*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

вторник, 3 августа 2010 г.

Поиск подстроки в строке: алгоритм Кнута-Морриса-Пратта

Мне понравилась идея недели борьбы с велосипедизмом, посему внесу свою лепту.

Один из частых вопросов, которые задают у нас в Блумберге на интервью в плане так называемого coding exercise (это когда надо на бумаге или на доске написать почти реальный кусок кода) - это поиск строки в подстроке. Это абсолютно жизненная задача.

Подавляющее число людей пишут первое, что приходит в голову - это два вложенных цикла, когда искомая строка последовательно "прикладывается" с каждой позиции исходной строки. Такой подход дает сложность O(M*N), и, очевидно, что в жизни он нереален, если строки более менее длинные. Хотя все при этом знают, что любой hex-вьювер спокойно ищет в огромных файлах за явно линейное время.

Итак, для эффективного поиска строки в подстроке есть алгоритм Кнута-Морриса-Пратта, который решает проблему не за O(N*M), а за O(N+M).

Построенный на префикс-функции, данный алгоритм является классичесим примером динамического программирования, когда результаты решения задачи малой размерности используются для решения задачи большей размерности.

P.S. Сразу скажу, у нас никто не просит по памяти писать КМП. И если человек после написания простого O(N^2) решения также скажет, что есть метод быстрее, и сможет описать его идею - этого вполне достаточно.

16 комментариев:

  1. Если честно, то алгоритм с двумя циклами - вовсе не первое, что пришло мне в голову. В голову мне пришло найти первый символ, а затем последовательно сравнивать следуюшие до первого несовпадения, причем лучше даже начиная с последнего.

    ОтветитьУдалить
  2. Советую также прочитать про алгоритм Бойера — Мура http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0

    Он более сложен зато оптимален. Крме того его можно использовать для поиска подстроки с игнорированием региста.

    ОтветитьУдалить
  3. -- Дмитрий Scriptin комментирует...
    В голову мне пришло найти первый символ, а затем последовательно сравнивать следуюшие до первого несовпадения, причем лучше даже начиная с последнего.

    Это и будет 2 вложеных цикла со сложностью О(M*N)

    ОтветитьУдалить
  4. @Дмитрий Scriptin: Это все равно O(N^2), как ни крути.

    ОтветитьУдалить
  5. У вас в Блумберге просто наверное алгоритмистов ищут, а не программистов. Разные отрасли совершенно. Это как под одну гребенку ровнять системного программиста, активно пишущего драйвера и программера БД.
    После прочтения только названия алгоритм Кнута-Морриалгоритма уже какой-то комплекс вырабатывается. :)

    ОтветитьУдалить
  6. @kostiantyn: Радикально с вами не согласен. В Блумберге ищут не программистов-кодеров, а инженеров, которые понимают сложность вещей. Например, если человек не помнит на память алгоритм КМП, но знает, что он есть, какова его идея и его свойства, то все хорошо. Но если человек, претендующий на позицию разработчика на С++, говорит, что НЕ знает, как устроен std::map изнутри, или не дай бог говорит, что там внутри hash-таблица и время доступа к элементу мэпа константно, то это будет на 100% отказ. Грамотный инженер может не помнить алгоритмы целиком, но обязан знать об их существовании и представлять их свойства и класс задач ими решаемый.

    ОтветитьУдалить
  7. Здраствуйте коллеги, я тут посмотрел алгоритм "префикс-функции" и один вопрос не даёт мне спокойно жить.

    type Arr = array of LongInt;
    function compute_prefix_function(s:string):Arr;
    var k,i,l:LongInt;
    begin
    l := Length(s);
    SetLength(Result, 1 + l);
    Result[0] := 0;
    Result[1] := 0;
    k := 0;
    for i := 2 to l do
    begin
    while (k > 0) and (s[k+1] <> s[i]) do
    k := Result[k];
    if s[k+1] = s[i] then
    Inc(k);
    Result[i] := k;
    end;
    end;

    Зачем этот кусок кода:
    while (k > 0) and (s[k+1] <> s[i]) do
    k := Result[k];
    если можно просто
    if (k > 0) and (s[k+1] <> s[i]) then
    k := 0;

    Спасибо.

    ОтветитьУдалить
  8. Извините за форматирование, в окне комментария он был отформатирован.

    ОтветитьУдалить
  9. @Yura: это откуда такое следствие интересное у Вас получилось? тот кусок кода, который у Вас вызывает вопрос выполняется несколько раз, изменяя k. Ваш вариант выполнится только один раз, просетапив переменную в 0.

    ОтветитьУдалить
  10. @Kostiantyn:

    То, что я написал:
    if (k > 0) and (s[k+1] <> s[i]) then
    k := 0;
    обьясняется очень просто, обнуляем счётчик префикса если следующий символ в текущем префиксе не равен следующиму символу в заданой последовательности. Как по мне вполне логично.

    А вот смысл цыкла:
    while (k > 0) and (s[k+1] <> s[i]) do
    k := Result[k];
    Мне не понятен.
    Может кто то может подсказать.

    Спасибо.

    ОтветитьУдалить
  11. Что насчёт такая модификация алгоритма поиска?

    char str[] = "abrakadabra";
    char substr[] = "bra";

    char subhex = 0;
    char temphex = 0;
    for (int i = 0; i < sizeof(substr); i++)
    {
    subhex ^= substr[i];
    temphex ^= str[i];
    }

    for (int i = 0; i < sizeof(str)-sizeof(substr); i++)
    {
    if (temphex == subhex)
    {
    // Найдено нечеткое совпадение,
    // необходимо проверить точным сравнением ...
    }

    // Выкидываем из XOR-суммы первый символ предполагаемой подстроки
    temphex ^= str[i];
    // добавляем к XOR-сумме последний символ предполагаемой подстроки
    temphex ^= str[i + sizeof(substr)];
    }

    Можно что-нить получше XOR-а использовать))
    Ушёл читать википедию про КМП ...

    ОтветитьУдалить
  12. Это выглядит как некоторое кеширование, которoе все равно на worse case'ах может работать O(N^2).

    ОтветитьУдалить
  13. Скорее хэширование, а не кэширование. Можно уменьшить число worse case-ов, если использовать несколько типов одновременно, например XOR и сумму. Понятно, что существует и худший случай.

    ОтветитьУдалить
  14. 2Yura Там действитель подходит if, потому что либо мы туда не заходим если патерны совпадают, либо заходим один раз и сразу вываливаемся, так как j становится равной 0 (если патерны не совпадают то соответствующий j елемент префиксной функции будет 0)

    ОтветитьУдалить
  15. Этот комментарий был удален автором.

    ОтветитьУдалить
  16. Извиняюсь ошибся не всегда j превращается в 0, только на простых примерах, на таком примере это не так :
    var a = FindSubstring("abciidabcabciidabcdabcabciidabciidabciidabciidababciidabcdeciidabciidabciid", "abciidabcde");

    ОтветитьУдалить