УДК 004.04

СРАВНЕНИЕ ПРОСТОГО АЛГОРИТМА ПОИСКА ПОДСТРОКИ В СТРОКЕ С АЛГОРИТМОМ КНУТА-МОРИСА-ПРАТТА С ПРИМЕРАМИ РЕАЛИЗАЦИИ АЛГОРИТМОВ НА ЯЗЫКЕ C++

Горденко Мария Константиновна
Национальный исследовательский университет «Высшая школа экономики»

Аннотация
На сегодняшний день поиск информации является основной задачей компьютера. Поиск заданной подстроки в строке – простая, но важная задача для современных поисковых систем, программ по работе с базами данных и т.д.
Существует немалое количество алгоритмов анализа строк, в том числе и алгоритмы поиска заданной подстроки в строке. В данной статье приводится два алгоритма поиска подстроки в строке: алгоритм Кнута-Мориса-Пратта и простой алгоритм с реализацией на языке C++.

Ключевые слова: алгоритм, алгоритм Кнута-Мориса-Пратта, подстрока, поиск строки, поисковая система, строка


THE COMPARISON OF A SIMPLE SEARCH SUBSTRING ALGORITHM WITH KNUTH-MORRIS-PRATT ALGORITHM WITH EXAMPLES OF IMPLEMENTATION ON C++

Gordenko Maria Konstantinovna
National research university «Higher school of economics»

Abstract
To date, information retrieval is the main task of the computer. Search the specified substring in a string - a simple but important task for today's search engines, programs to work with databases, etc.
There is a considerable amount of analysis algorithms lines, including search algorithms given substring. This article provides two search algorithm substring: Knuth-Morris-Pratt algorithm and simple algorithm and the implementations of them on C++.

Рубрика: 05.00.00 ТЕХНИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Горденко М.К. Сравнение простого алгоритма поиска подстроки в строке с алгоритмом Кнута-Мориса-Пратта с примерами реализации алгоритмов на языке C++ // Современные научные исследования и инновации. 2015. № 2. Ч. 1 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2015/02/46825 (дата обращения: 02.06.2017).

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

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

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

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

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

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

a b c a a b c a b b
a b c
a b c
a b c
a b c
a b c
a b c
a b c
a b c

На языке 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 – Пример работы алгоритма Кнута-Мориса-Пратта

i

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

T

a

b

a

b

a

b

a

b

c

c

a

b

d

a

b

a

b

W

a

b

a

b

a

b

a

b

a

b

a

b

a

b

a

b

a

b

a

b

a

b

a

b

a

b

a

b

a

b

a

b

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

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.


Все статьи автора «Горденко Мария Константиновна»


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: