KMP算法模板

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的ne数组：ne[i]数组计算匹配串的公共前后缀的最大长度
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        cout<<i-m<<" ";
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

简单入门题

Simpsons’ Hidden Talents

/*
题意：给你两个串，问你s1的前缀和s2的后缀最长公共部分是多少。
否则输出0 
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
char s[maxn],t[maxn];
int n,m,nxt[maxn];
int main() {
    while (~scanf("%s%s",s+1,t+1)){
        n=strlen(s+1);m=strlen(t+1);
        int ans=0;
        for (int i=2,j=0;i<=n;i++){
            while (j&&s[i]!=s[j+1])j=nxt[j];
            if (s[i]==s[j+1])j++;
            nxt[i]=j;
        }
        for (int i=1,j=0;i<=m;i++){
            while (j&&s[j+1]!=t[i])j=nxt[j];
            if (s[j+1]==t[i])j++;
            if (i==m)ans=j;
            if (j==n){
                j=nxt[j];
            }
        }
        if (!ans)puts("0");
        else{
            for (int i=1;i<=ans;i++)printf("%c",s[i]);
            printf(" ");
            printf("%d\n",ans);
        }
    }
    return 0;
}

剪花布条

#include<bits/stdc++.h>
using namespace std;
const int N =1005;
char a[N],b[N],ne[N];
int main(){
    while (1){
        cin>>a+1;
        if(a[1]=='#') break;
        cin>>b+1;
        int x=strlen(a+1);
        int y=strlen(b+1);
        for(int i=2,j=0;i<=y;i++){
            while(j&&b[i]!=b[j+1]) j=ne[j];
            if(b[i]==b[j+1]) j++;
            ne[i]=j;
        }
        int cnt=0;
        for(int i=1,j=0;i<=x;i++){
            while(j&&a[i]!=b[j+1]) j=ne[j];
            if(a[i]==b[j+1]) j++;
            if(j==y){
                cnt++;
                j=0;//
            }
        }
        cout<<cnt<<endl;
    }
} 

字符串乘方

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=110;

int ne[N];
int n;

int main()
{
    char s[N];
    while(cin>>s+1 && s[1]!='.')
    {
        int n=strlen(s+1);
        for(int i=2,j=0;i<=n;i++)
        {
            while(j && s[i]!=s[j+1]) j=ne[j];
            if(s[i]==s[j+1]) j++;
            ne[i]=j;
        }
        cout<< n/(n-ne[n]) <<endl;
    }
    return 0;
}