Последовательное точное сравнение строк: различия между версиями

Этап поиска алгоритмов сравнения строк работает следующим образом. Вначале он выравнивает оевые концы образца и текста, затем сравнивает выровненные символы текста и образца – эта операция называется попыткой или сканированием – а после обнаружения совпадения всего образца либо несовпадения перемещает образец вправо. Эта процедура повторяется до тех пор, пока правый конец образца не выйдет за правый конец текста. Фаза сканирования может рассматриваться как операция над текстом сквозь окно, размер которого чаще всего совпадает с длиной образца. Данный вид обработки называется механизмом сканирования и сдвига. Различные стратегии сканирования окна легли в основу разных алгоритмов, обладающих различными свойствами и преимуществами.

Алгоритм решения задачи ESM полным перебором выполняет проверку вхождения P на каждой позиции j строки T, где 1 < j < n — m + 1. Ему не требуется этап предварительной обработки. Этот алгоритм требует O(mn) времени и константной дополнительной памяти и в среднем производит O(n) сравнений символов. Его можно сравнить со следующими границами.

Теорема 1 (Коул и коллеги 1995 [ ]). Минимальное количество сравнений символов для решения задачи ESM в наихудшем случае не превышает n + 9/(4m)(n — m) и может быть сделано менее и + 8/(3(m+.