KMP模板（洛谷P3375）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 string s1, s2;
 4 vector<int> find_next(vector<int> next, string s)
 5 {
 6     int i = 1, prefix = 0, len = s.length();
 7     while (i < len)
 8     {
 9         if (s[prefix] == s[i])
10         {
11             ++prefix, ++i;
12             next.push_back(prefix);
13         }
14         else if (prefix == 0)
15         {
16             next.push_back(0);
17             ++i;
18         }
19         else
20             prefix = next[prefix - 1];
21     }
22     return next;
23 }
24 void kmp(vector<int> next, string s1, string s2)
25 {
26     int len1 = s1.length(), len2 = s2.length();
27     int i = 0, j = 0;
28     while (i < len1)
29     {
30         while (j && s1[i] != s2[j])
31             j = next[j - 1];
32         if (s1[i] == s2[j])
33             ++j;
34         ++i;
35         if (j == len2)
36             cout << i - j + 1 << endl;
37     }
38 }
39 int main()
40 {
41     cin >> s1 >> s2;
42     vector<int> next(1);
43     next = find_next(next, s2);
44     kmp(next, s1, s2);
45     for (auto i : next)
46         cout << i << " ";
47 }