Мне понравилась идея недели борьбы с велосипедизмом, посему внесу свою лепту.
Один из частых вопросов, которые задают у нас в Блумберге на интервью в плане так называемого coding exercise (это когда надо на бумаге или на доске написать почти реальный кусок кода) - это поиск строки в подстроке. Это абсолютно жизненная задача.
Подавляющее число людей пишут первое, что приходит в голову - это два вложенных цикла, когда искомая строка последовательно "прикладывается" с каждой позиции исходной строки. Такой подход дает сложность O(M*N), и, очевидно, что в жизни он нереален, если строки более менее длинные. Хотя все при этом знают, что любой hex-вьювер спокойно ищет в огромных файлах за явно линейное время.
Итак, для эффективного поиска строки в подстроке есть алгоритм Кнута-Морриса-Пратта, который решает проблему не за O(N*M), а за O(N+M).
Построенный на префикс-функции, данный алгоритм является классичесим примером динамического программирования, когда результаты решения задачи малой размерности используются для решения задачи большей размерности.
P.S. Сразу скажу, у нас никто не просит по памяти писать КМП. И если человек после написания простого O(N^2) решения также скажет, что есть метод быстрее, и сможет описать его идею - этого вполне достаточно.
вторник, 3 августа 2010 г.
Подписаться на:
Комментарии к сообщению (Atom)
Сообщения
Если честно, то алгоритм с двумя циклами - вовсе не первое, что пришло мне в голову. В голову мне пришло найти первый символ, а затем последовательно сравнивать следуюшие до первого несовпадения, причем лучше даже начиная с последнего.
ОтветитьУдалитьСоветую также прочитать про алгоритм Бойера — Мура 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
ОтветитьУдалитьОн более сложен зато оптимален. Крме того его можно использовать для поиска подстроки с игнорированием региста.
-- Дмитрий Scriptin комментирует...
ОтветитьУдалитьВ голову мне пришло найти первый символ, а затем последовательно сравнивать следуюшие до первого несовпадения, причем лучше даже начиная с последнего.
Это и будет 2 вложеных цикла со сложностью О(M*N)
@Дмитрий Scriptin: Это все равно O(N^2), как ни крути.
ОтветитьУдалитьУ вас в Блумберге просто наверное алгоритмистов ищут, а не программистов. Разные отрасли совершенно. Это как под одну гребенку ровнять системного программиста, активно пишущего драйвера и программера БД.
ОтветитьУдалитьПосле прочтения только названия алгоритм Кнута-Морриалгоритма уже какой-то комплекс вырабатывается. :)
@kostiantyn: Радикально с вами не согласен. В Блумберге ищут не программистов-кодеров, а инженеров, которые понимают сложность вещей. Например, если человек не помнит на память алгоритм КМП, но знает, что он есть, какова его идея и его свойства, то все хорошо. Но если человек, претендующий на позицию разработчика на С++, говорит, что НЕ знает, как устроен std::map изнутри, или не дай бог говорит, что там внутри hash-таблица и время доступа к элементу мэпа константно, то это будет на 100% отказ. Грамотный инженер может не помнить алгоритмы целиком, но обязан знать об их существовании и представлять их свойства и класс задач ими решаемый.
ОтветитьУдалитьЗдраствуйте коллеги, я тут посмотрел алгоритм "префикс-функции" и один вопрос не даёт мне спокойно жить.
ОтветитьУдалить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;
Спасибо.
Извините за форматирование, в окне комментария он был отформатирован.
ОтветитьУдалить@Yura: это откуда такое следствие интересное у Вас получилось? тот кусок кода, который у Вас вызывает вопрос выполняется несколько раз, изменяя k. Ваш вариант выполнится только один раз, просетапив переменную в 0.
ОтветитьУдалить@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];
Мне не понятен.
Может кто то может подсказать.
Спасибо.
Что насчёт такая модификация алгоритма поиска?
ОтветитьУдалить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-а использовать))
Ушёл читать википедию про КМП ...
Это выглядит как некоторое кеширование, которoе все равно на worse case'ах может работать O(N^2).
ОтветитьУдалитьСкорее хэширование, а не кэширование. Можно уменьшить число worse case-ов, если использовать несколько типов одновременно, например XOR и сумму. Понятно, что существует и худший случай.
ОтветитьУдалить2Yura Там действитель подходит if, потому что либо мы туда не заходим если патерны совпадают, либо заходим один раз и сразу вываливаемся, так как j становится равной 0 (если патерны не совпадают то соответствующий j елемент префиксной функции будет 0)
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьИзвиняюсь ошибся не всегда j превращается в 0, только на простых примерах, на таком примере это не так :
ОтветитьУдалитьvar a = FindSubstring("abciidabcabciidabcdabcabciidabciidabciidabciidababciidabcdeciidabciidabciid", "abciidabcde");