I'm sorry my head is about to explode...

Question surface.

Spicy chicken KMP algorithm. I only know that my code in the evening is wildly transformed between the simplified version and the official version, and I even write the simplified version first, then the official version, then the simplified version, then the official version.

In short, KMP is an algorithm for string comparison, and it can find the position of the string.

By the way, this question must use the official version of KMP, because to output the next array, and the next array of this question is the next array found under the official version of KMP code.

 1 #include<set>
 2 #include<map>
 3 #include<list>
 4 #include<queue>
 5 #include<stack>
 6 #include<string>
 7 #include<cmath>
 8 #include<ctime>
 9 #include<vector>
10 #include<bitset>
11 #include<memory>
12 #include<utility>
13 #include<cstdio>
14 #include<sstream>
15 #include<iostream>
16 #include<cstdlib>
17 #include<cstring>
18 #include<algorithm>
19 using namespace std;
20 
21 int lena,lenb;
22 int next[1000005];
23 char z[1000005],y[1000005];//Two strings
24 
25 void pre(){//For the preprocessing of the next array of substrings, that is, the KMP of a string to itself
26     int j=0;
27     next[1]=0;
28     for(int i=1;i<lenb;i++){
29         while(j>0&&y[i+1]!=y[j+1]){
30             j=next[j];
31         }
32         if(y[i+1]==y[j+1]){
33             j++;
34         }
35         next[i+1]=j;
36     }
37 }
38 
39 void KMPMatch(){//KMP algorithm official program
40     int j=0;
41     for(int i=0;i<lena;i++){
42         //printf("%d %d\n",i,j);
43         while(y[j+1]!=z[i+1]&&j>0){
44             j=next[j];
45         }
46         //cout<<z[j+1]<<' '<<y[i+1]<<endl;
47         if(y[j+1]==z[i+1]){
48             j++;
49         }
50         if(j==lenb){//If the substring is matched, the output position
51             printf("%d\n",i+1-j+1);
52             i=i+1-j;//Move the subscript to the first subscript + 1 of the substring
53             j=0;
54         }
55         //printf("%d %d\n",i,j);
56     }
57 }
58 
59 int main(){
60     cin>>z+1;
61     cin>>y+1;
62     lena=strlen(z+1);
63     lenb=strlen(y+1);
64     pre();//The next array is preprocessed. Here, the function name of a dalao problem solution is used for reference.
65     KMPMatch();//KMP
66     for(int i=1;i<=lenb;i++){
67         printf("%d ",next[i]);
68     }
69     return 0;
70 }

That's it. I'm going to sleep. If I don't, I'm going to die...