KMP

void get_next()
{
    int j;
    memset(next,0,sizeof(next));
    next[0]=j=-1;
    l1=strlen(c1);
    for (int i=1; i<l1; i++)
    {
        while (j!=-1&&c1[i]!=c1[j+1])
        {
            j=next[j];
        }
        if (c1[i]==c1[j+1]) j++;
        next[i]=j;
    }
}

void Kmp()
{
    get_next();
    l2=strlen(c2);
    int j=-1;
    for (int i=0; i<l2; i++)
    {
        while (j!=-1&&c1[j+1]!=c2[i])
        {
            j=next[j];
        }
        if (c1[j+1]==c2[i]) j++;
        if (j==l1-1)
        {
            ans++;
            j=-1;//不重叠J=next[j]
    
        
        }
    }
}

 1 #include<cstring>
 2 #include<stack>
 3 #include<cstdio>
 4 using namespace std;
 5 
 6 const int N=400010;
 7 char c[N];
 8 int n,m,i,j,next[N],l;
 9 stack<int>Stack;
10 void get_next(){
11     memset(next,0,sizeof(next));
12     next[0]=j=-1;
13     l=strlen(c);
14     for (int i=1;i<l;i++){
15         while (j!=-1&&c[i]!=c[j+1]){
16             j=next[j];
17         }
18         if (c[i]==c[j+1]) j++;
19         next[i]=j;
20     }
21 }
22 
23 
24 
25 int main(){
26     while (~scanf("%s",c)){
27         get_next();
28         while (!Stack.empty()){
29             Stack.pop();
30         }
31         int ll=l;
32         l=next[l-1];
33         while (l>=0){
34             Stack.push(l+1);
35             l=next[l];
36         }
37         while (!Stack.empty()){
38             printf("%d ",Stack.top());
39             Stack.pop();
40         }
41         printf("%d
",ll);
42     }
43 }

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int N=2000000;
 5 int next1[N],l1;
 6 char c1[N];
 7 
 8 void get_next()
 9 {
10     int j;
11     memset(next1,0,sizeof(next1));
12     next1[0]=j=-1;
13     l1=strlen(c1);
14     for (int i=1; i<l1; i++)
15     {
16         while (j!=-1&&c1[i]!=c1[j+1])
17         {
18             j=next1[j];
19         }
20         if (c1[i]==c1[j+1]) j++;
21         next1[i]=j;
22     }
23 }
24 
25 int main(){
26     while (scanf("%s",c1)){
27         get_next();
28         if (c1[0]=='.') {
29             break;
30         }
31         int k=l1-1-next1[l1-1];
32         if (l1%k==0){
33             printf("%d
",l1/k);
34         }else{
35             printf("1
");
36         }
37     }
38 }

View Code

 1 #include<cstring>
 2 #include<cstdio>
 3 using namespace std;
 4 const int N=1e7+10;
 5 int next[N],l2,l1;
 6 char c1[N],c2[N];
 7 void get_next(){
 8     int j;
 9     memset(next,0,sizeof(next));
10     next[0]=j=-1;
11     l1=strlen(c1);
12     for (int i=1;i<l1;i++){
13         while (j!=-1&&c1[i]!=c1[j+1]){
14             j=next[j];
15         }
16         if (c1[i]==c1[j+1]) j++;
17         next[i]=j;
18     }
19 }
20 
21 
22 int main(){
23     int t;
24     scanf("%d",&t);
25     while (t--){
26         int ans=0;
27         scanf("%s",c1);
28         get_next();
29         scanf("%s",c2);
30         l2=strlen(c2);
31         int j=-1;
32         for (int i=0;i<l2;i++){
33             while (j!=-1&&c1[j+1]!=c2[i]){
34                 j=next[j];
35             }
36             if (c1[j+1]==c2[i]) j++;
37             if (j==l1-1){
38                 ans++;
39                 j=next[j];
40             }
41         }
42         printf("%d
",ans);
43     }
44 }

View Code

 1 #include<cstring>
 2 #include<cstdio>
 3 using namespace std;
 4 const int N=1e7+10;
 5 int next[N],l2,l1,a[N];
 6 char c1[N],c2[N];
 7 void get_next()
 8 {
 9     int j;
10     memset(next,0,sizeof(next));
11     next[0]=j=-1;
12     l1=strlen(c1);
13     for (int i=1; i<l1; i++)
14     {
15         while (j!=-1&&c1[i]!=c1[j+1])
16         {
17             j=next[j];
18         }
19         if (c1[i]==c1[j+1]) j++;
20         next[i]=j;
21     }
22 }
23 
24 
25 int main()
26 {
27     int t;
28     scanf("%d",&t);
29     while (t--)
30     {
31         int ans=0;
32         scanf("%s",c2);
33         scanf("%s",c1);
34         get_next();
35         l2=strlen(c2);
36         int j=-1;
37         for (int i=0; i<l2; i++)
38         {
39             while (j!=-1&&c1[j+1]!=c2[i])
40             {
41                 j=next[j];
42             }
43             if (c1[j+1]==c2[i]) j++;
44             if (j==l1-1)
45             {
46                 ans++;
47                 a[ans]=i-l1+1+1;
48                 j=next[j];
49             }
50         }
51         if (!ans)
52         {
53             printf("Not Found
");
54         }
55         else
56         {
57             printf("%d
",ans);
58             for (int i=1; i<ans; i++)
59             {
60                 printf("%d ",a[i]);
61             }
62             printf("%d
",a[ans]);
63         }
64         if (t){
65             printf("
");
66         }
67     }
68 }

View Code

 1 #include<cstring>
 2 #include<cstdio>
 3 using namespace std;
 4 const int N=1e7+10;
 5 int next[N],l2,l1;
 6 char c1[N],c2[N];
 7 void get_next(){
 8     int j;
 9     memset(next,0,sizeof(next));
10     next[0]=j=-1;
11     l1=strlen(c1);
12     for (int i=1;i<l1;i++){
13         while (j!=-1&&c1[i]!=c1[j+1]){
14             j=next[j];
15         }
16         if (c1[i]==c1[j+1]) j++;
17         next[i]=j;
18     }
19 }
20 
21 
22 int main(){
23     int t,ans=0;
24         scanf("%s",c2);
25         scanf("%s",c1);
26         get_next();
27 
28         l2=strlen(c2);
29         int j=-1;
30         for (int i=0;i<l2;i++){
31             while (j!=-1&&c1[j+1]!=c2[i]){
32                 j=next[j];
33             }
34             if (c1[j+1]==c2[i]) j++;
35             if (j==l1-1){
36                 ans++;
37                 j=-1;//不能重复
38             }
39         }
40         printf("%d
",ans);
41     }

View Code