Изменения
Нет описания правки
При предподсчёте перебирается <tex> | \Sigma | ^k </tex> (где <tex> | \Sigma | </tex> — мощность алфавита) возможных подстрок первой строки и столько же — второй строки. Для каждой возможной подстроки обеих строк перебирается по <tex> 2^{k - 1} </tex> битовых масок. Для самого предподсчёта требуется время <tex> O(k^2) </tex>. Дальнейший алгоритм поиска НОП требует <tex> O \left ( \frac{n^2}{k^2} \right ) </tex>. Тогда суммарное время работы алгоритма составляет <tex> O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 + \frac{n^2}{k^2} \right ) </tex>.
Понятно, что для получения выигрыша в производительности по сравнению с обычным алгоритмом необходимо, чтобы первое слагаемое не превышало второе. Найдём <tex> k </tex>, решив неравенство <tex> |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 \leqslant \frac{n^2}{k^2} </tex>. Оно преобразуется к виду <tex> \left ( 2 | \Sigma | \right ) ^{2k} \cdot \frac{1}{4} \cdot k^4 \leqslant n^2 </tex>. Далее извлекаем корень: <tex> \left ( 2 | \Sigma | \right ) ^k \cdot k^2 \leqslant 2n </tex>. Прологарифмируем: <tex> k \log {2 | \Sigma |} + 2 \log k \leqslant \log 2 + \log n </tex>. Отсюда <tex> k < \frac{\log n}{1 + \log {1 + | \Sigma |}}</tex>
== Источники ==
