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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>
#include <string>
#define forn(i,n) for(int i=0;i<n;i++)
using namespace std;
string s2,s1;
vector<int> prefix_function (string s) {
    int n = (int) s.length();
   
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
       
        while ((j > 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<int> p=prefix_function (s1);


forn(i,p.size()){
    if(p[i]==s2.size()){
        cout<<i-2*s2.size()+1<<" ";
    }
}

    return 0;
}

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

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

  • на Delphi

  • на Java

  • на C++