1498. КМП

Найти все вхождения строки word в строку text.

Вход. В первой строке записана строка text, во второй - строка word. Длины строк больше 0 и меньше 50000, строки содержат только латинские буквы.

Выход. Выведите номера символов, начиная с которых строка word входит в строку text, в порядке возрастания. Как это обычно принято у программистов, нумерация символов начинается с нуля.

Пример входа	Пример выхода
ababbababa aba	0 5 7

РЕШЕНИЕ

строки – Кнут-Моррис-Пратт

Анализ алгоритма

В задаче необходимо реализовать алгоритм Кнута-Морриса-Пратта поиска в тексте подстроки.

Реализация алгоритма

Первую строку text будем считать текстом, а вторую word – шаблоном. Хранить их будем соответственно в символьных массивах text и word. Массив p содержит значения префикс - функции шаблона, который заполняется функцией MaxBorderArray. В массиве pos будем хранить номера позиций, с которых строка word входит в строку text, в порядке возрастания.

#define MAX 50010

char text[MAX];

char word[MAX];

int p[MAX], pos[MAX];

Функция MaxBorderArray вычисляет в массиве p префикс - функцию строки s.

void MaxBorderArray(char *s)

{

int i, j, len = strlen(s);

p[0] = 0;

for(i = 1; i < len; i++)

{

j = p[i - 1];

while ((j > 0) && (s[i] != s[j])) j = p[j - 1];

if (s[i] == s[j]) j++;

p[i] = j;

}

}

Функция kmp реализует алгоритм Кнута-Морриса-Пратта. Все индексы начала вхождения строки word в текст text сохраняются в массиве pos.

void kmp(char *word, char *text)

{

int i, j;

int textLen = strlen(text), wordLen = strlen(word);

MaxBorderArray(word);

for(i = j = 0; i < textLen; i++)

{

while(j && (text[i] != word[j])) j = p[j - 1];

if (text[i] == word[j]) j++;

Если индекс j дошел до последнего символа слова word (стал равным wordLen), то слово word найдено в тексте. При этом найденное слово начинается в позиции i – j + 1 (индексация начинается с нуля).

if (j == wordLen) pos[ptr++] = i - j + 1;

}

}

Основная часть программы. Читаем входные строки и запускаем алгоритм Кнута-Морриса-Пратта.

gets(text);

gets(word);

kmp(word,text);

Выводим найденные позиции совпадения.

for(i = 0; i < ptr; i++)

{

if (i) printf(" ");

printf("%d",pos[i]);

}

printf("\n");