Постановка задачи: Дан некий текст T и образец слова W. Необходимо найти все вхождения образца слова W в текст T.

Начнем рассматривать алгоритмы от простого к сложному. Стоит отметить, что чем сложнее алгоритм тем его временная сложность меньше.

        1.     Простой алгоритм решения.

Необходимо посимвольно прикладывать образец текста W к самому тексту T, начиная с первой позиции. Таким образом, возможно две ситуации: либо символы совпадут, либо не совпадут, начиная с какой-то позиции. Если символы совпали, то это совпадение фиксируется. Затем образец текста сдвигается на один символ вправо и снова начинается сравнение, при этом нет учета результата предыдущих сравнений. 

Например, пусть дан текст T = abcaabcabb и слово W = abc, то наглядо алгоритм можно представить следующим образом:

Таблица 1 – Пример работы простого алгоритма

На языке C++ алгоритм может быть реализован следующим образом:

int find_substrings(string S, string W) {

unsigned int i, j;

int number = 0;

for (i = 0; i < S.length() – W.length() + 1; i++) {

j = 0;

while ((j < W.length()) && (W[j] == S[i + j])) {

j = j + 1;

}

if (j == W.length())

{

cout << “Вхождение слова ” << W << ” , с номера позиции: ” << i << endl;

number++;

}

}

return number;

}

Здесь функция find_substrings возвращает количество вхождений подстроки в строку, а также выводит в консольное окно номера позиций, с которых начинается вхождение.

Очевидно, что временная сложность алгоритма имеет значение – O(S.length()W.length())

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

Как видно из предыдущего алгоритма, существует очень много лишних сравнений, которых можно избежать, используя методы предварительного анализа строк.

В 1970 году Д. Кнут, Д. Морис и В. Пратт пришли к идее создания алгоритма, который способен найти подстроку в строке за количество сравнений, эквивалентных длине строки. Идея алгоритма состоит в том, чтобы не прикладывать подстроку к строке со сдвигом всего в один символ, а максимально увеличить это расстояние, сократив таким образом количество сравнений.

Первоначально необходимо найти все префиксы строки W, равные ее суффиксам, т.е. необходимо найти грани текста. Логично предположить, что для каждой позиции j в слове будет своя величина грани и величина граней не зависит от подстроки, а зависит только от строки W, поэтому необходимо предварительно вычислить массив (коллекцию) значений граней подстроки W.

Алгоритмы поиска граней в строке подробно описаны в книге С.М. Окулова [1].

Ниже приведена реализация одного из самых эффективных по количеству сравнений алгоритмов поиска граней, требующий количество сравнений эквивалентных числу символов в исследуемой строке.

int* max_border_array(string T) {

int i, n = T.length(), t;

int *br = new int[n];

br[0] = 0;

for (i = 1; i < n; i++) {

t = br[i - 1];

while ((t > 0) && (T[i] != T[t])) {

t = br[t - 1];

}

if (T[i] == T[t]) {

br[i] = t + 1;

} else {

br[i] = 0;

}

}

return br;

}

Перед началом работы алгоритма Кнута-Мориса-Пратта необходимо вычислить массив граней подстроки W. А затем, прикладывать подстроку к строке со сдвигом , где  – текущая позиция в слове,  -  величина грани слова в позиции .

Рассмотрим работу алгоритма на примере:

T = ababababccabdabab

W = abab

Массив граней br слова W = (0, 0, 1, 2)

Таблица 2 – Пример работы алгоритма Кнута-Мориса-Пратта

Реализация алгоритма Кнута-Мориса-Пратта на языке С++:

vector<int> KMP(string str, string sub, int* br) {

vector<int> solution;

int poz = 0;

for (int i = 0; i < str.size(); i++) {

while (poz == sub.size() || (poz > 0 && sub[poz] != str[i])) {

poz = br[poz - 1];

if (sub.size() – poz > str.size() – i)

break;

}

if (str[i] == sub[poz]) {

poz++;

}

if (poz == sub.size()) {

solution.push_back(i – poz + 1);

}

}

return solution;

}

Таким образом, временная сложность алгоритма Кнута-Мориса-Пратта – O(S.length()W.length()), что гораздо эффективнее простого алгоритма поиска подстроки в строке.

1. Окулов С.М. Алгоритмы обработки строк. – М.: БИНОМ. Лаборатория знаний, 2009.
2. Семинар 13. Строки в С++. Алгоритм Кнута-Морриса-Пратта. – ВШЭ.: Построение и анализ алгоритмов, 2014.

Все статьи автора «Maria_hse»