Алгоритм Кнута-Морриса-Пратта (Реализация на C++)

C++   9 декабря 2012  Автор статьи:  

В данной статье мы реализуем алгоритм КМП. Данный алгоритм умеет находить все вхождения подстроки в текст. Для этого он использует префикс — функцию, которая считает, сколько символов совпало у префикса строки и у строки, заканчивающимся в i-ой позиции. Таким образом, если сложить образец и текст, а затем подсчитать на данном объекте префикс функцию, то мы получим вхождения образца в текст, если в данной позиции длина образца совпадает с значением префикс функции. На вход мы примем образец и текст, а на выход отдадим позиции входа образца в текст:

#include
#include
#include
#define forn(i,n) for(int i=0;i prefix_function (string s) {
int n = (int) s.length();

vector pi (n);
for (int i=1; i 0) && (s[i] != s[j] || j==s2.size() || i==s2.size()))
j = pi[j-1];
if (s[i] == s[j] && i!=s2.size() && j!=s2.size()) ++j;
pi[i] = j;
}
return pi;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

cin>>s2>>s1;
s1=s2+'#'+s1;

vector p=prefix_function (s1);

forn(i,p.size()){
if(p[i]==s2.size()){
cout<

Тест:
Входные данные:
aba
ababacaba
Выходные данные:
1 3 7

Научиться программировать

  • на Delphi

  • на Java

  • на C++