题目链接：https://www.luogu.com.cn/problem/P3375
ac代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include<set> 8 #include 9 #include 10 #include 11 #include<string> 12 #define ll long long 13 #define ull unsigned long long 14 #define inf 0x3f3f3f3f 15 #define inff 0x7fffffff 16 using namespace std; 17 const int N = 100000 + 10; 18 const int M = 1000000 + 10; 19 const ll mod = 1e9 + 7; 20 21 char s[M], p[N]; 22 int next_kmp[N]; 23 24 void kmp_pre(int m) { 25 26 int i, j; 27 i = 0; 28 j = next_kmp[0] = -1; 29 while (i < m) { 30 while (j != -1 && p[i] != p[j]) j = next_kmp[j]; 31 next_kmp[++i] = ++j; 32 } 33 34 return; 35 } 36 37 int ans = 0; 38 39 void kmp(int n, int m) { 40 41 //int ans = 0; 42 int i, j; 43 i = 0, j = 0; 44 kmp_pre(m); 45 while (i < n) { 46 while (j != -1 && s[i] != p[j]) j = next_kmp[j]; 47 i++, j++; 48 if (j >= m) { 49 cout << i - m + 1 << "\n"; 50 ans++; 51 j = next_kmp[j]; 52 } 53 } 54 55 return; 56 //return ans; 57 } 58 59 60 int main() { 61 62 //int lenp, lens; 63 cin >> s; 64 cin >> p; 65 int lens = strlen(s); 66 int lenp = strlen(p); 67 kmp(lens, lenp); 68 //putchar('\n'); 69 //cout << ans << "\n"; 70 //cout << kmp(lens, lenp) << "\n"; 71 for (int i = 1; i <= lenp; i++) { 72 cout << next_kmp[i] << " "; 73 } 74 75 return 0; 76 }