模板——KMP

继续放。。。。

#include<stdio.h>
#include<cstring>
using namespace std;

const int MAXN = 1000005;
char a[MAXN];char b[MAXN];int next[MAXN];

int main(){
    scanf("%s%s",a,b);
    int lena = strlen(a);
    int lenb = strlen(b);
    int j=0,k=-1;next[0] = -1;
    while(j < lenb){
        if(k == -1 || b[j] == b[k]){
            j++;k++;
            next[j] = k;
        }
        else k = next[k];
    }
    j=0,k=0;
    while(j < lenb && k<lena){
        if(j == -1 || b[j] == a[k]){
            j++;k++;
        }
        else j = next[j];
        if(j == lenb){printf("%d\n",k-lenb+1);j = next[j];}
    }
    for(int i=1;i<=lenb;++i) printf("%d ",next[i]);
    return 0;
}

顺便放个\(Sunday\)的板。。

#include<stdio.h>
#include<cstring>

using namespace std;

const int MAXN = 10000005;
char a[MAXN];char b[MAXN];int shift[30];

inline void sunday(){
    int lena = strlen(a+1);
    int lenb = strlen(b+1);
    
    for(int i=0;i<26;++i){
        shift[i] = lenb;
    }
    
    for(int i=1;i<=lenb;++i){
        shift[b[i] - 'a'] = lenb - i + 1;
    }
    
    int l1=1;
    int l2=1;
    int head=1;
    while(l1 <= lena - lenb + 1){
        l2 = 1;
        while(a[l1] == b[l2]){
            l1++;l2++;
            if(l2 > lenb){
                printf("%d\n",l1 - l2 + 1);
                return ;
            }
        }
        if(head + lenb > lena) break;
        l1 += shift[a[head + lenb] - 'a'];
        head = l1;
    }
    puts("-1");return ;
}

int main(){
    scanf("%s%s",a+1,b+1);
    sunday();
    return 0;
}

模板——KMP

原文：https://www.cnblogs.com/lajioj/p/9479064.html