берём брутфорс: два вложенных цикла. Сложность перемножается. То есть O(n*m), где n — длина строки, а m — длина шаблона.
берём алгоритм Рабина-Карпа: Предварительные вычисления сложности O(m) и потом опять два цикла, причём вложенный практически не запускается в холостую. Если взять base и q очень большими (но всё же простыми) числами, влазящими в int32, то на практике внутренний цикл можно не запускать — с огромной вероятностью совпадение хеш-значений будет свидетельствовать о совпадении строк.
Таким образом, сложность алгоритма в среднем случае O(m+n), что меньше O(m*n). В худшем случае сложность будет O(n*m), хотя вероятность такого случая на практике крайне мала.
«умножение кода символа на экспоненциально зависящее от позиции этого самого символа»
извините, имел в виду «умножение кода символа на экспоненциально зависящее от позиции этого самого символа число»
про то, как перейти от брутфорса к МП, а от МП к КМП хотел в следующий раз обзор сделать… вот только не знаю — есть ли смысл, поскольку:
1) есть хорошие визуализации, вроде этой (спасибо el777 )
2) немногим это будет полезно
хотя…
я конечно стараюсь писать то, как я это представляю, ознакомившись с другими источниками. может быть кому-то будет интересна мелочь, которую он не замечал (в принципе это и есть повод писать и читать статьи — менять систему отсчёта для знакомых вещей так сказать).
одним словом — попробую написать что-то интересное или неочевидное в давно известном алгоритме
я написал, что это лишь вступление, а быстрые и эффективные методы интересны и самому. Но не начинать же с мегакрутых алгоритмов? хочется постепенно… с примитива
Chromium Version 28.0.1500.71 Built on Ubuntu 13.04, running on LinuxMint 15
стразу после этого приближения описывается, насколько оно неэффективно
берём брутфорс: два вложенных цикла. Сложность перемножается. То есть O(n*m), где n — длина строки, а m — длина шаблона.
берём алгоритм Рабина-Карпа: Предварительные вычисления сложности O(m) и потом опять два цикла, причём вложенный практически не запускается в холостую. Если взять base и q очень большими (но всё же простыми) числами, влазящими в int32, то на практике внутренний цикл можно не запускать — с огромной вероятностью совпадение хеш-значений будет свидетельствовать о совпадении строк.
Таким образом, сложность алгоритма в среднем случае O(m+n), что меньше O(m*n). В худшем случае сложность будет O(n*m), хотя вероятность такого случая на практике крайне мала.
извините, имел в виду «умножение кода символа на экспоненциально зависящее от позиции этого самого символа число»
private int GetHashOfString(string s, int q, int b)
{
int result = 0;
int length = s.Length;
for (int i = 0; i < length; i++)
result = (b * result + s[i]) % q;
return result;
}
Разве умножение кода символа на экспоненциально зависящее от позиции этого самого символа может дать симметричную хеш-функцию?
1) есть хорошие визуализации, вроде этой (спасибо el777 )
2) немногим это будет полезно
хотя…
я конечно стараюсь писать то, как я это представляю, ознакомившись с другими источниками. может быть кому-то будет интересна мелочь, которую он не замечал (в принципе это и есть повод писать и читать статьи — менять систему отсчёта для знакомых вещей так сказать).
одним словом — попробую написать что-то интересное или неочевидное в давно известном алгоритме
наверное…
Но это всего лишь введение, которое планируется продолжать более быстрыми и эффективными алгоритмами