字符串

KMP

#include <cstdio>
#include <cstring>
#define R register
const int MAXN=1000007;
int l,l1;
char s[MAXN],s1[MAXN];
int fail[MAXN];
inline void get_next()
{
    int p=0;
    for(R int i=2;i<=l;++i)
    {
        while(p>0&&s[i]!=s[p+1]) p=fail[p];
        if(s[i]==s[p+1]) p++;
        fail[i]=p;
    }
}

inline void kmp()
{
    int p=0;
    for(R int i=1;i<=l1;++i)
    {
        while(p>0&&s[p+1]!=s1[i]) p=fail[p];
        if(s[p+1]==s1[i]) p++;
        if(p==l)
        {
            printf("%d\n",i-l+1);
            p=fail[p];
        }
    }
}

int main()
{
    scanf("%s%s",s1+1,s+1);
    l=strlen(s+1);
    l1=strlen(s1+1);
    get_next();
    kmp();
    for(int i=1;i<=l;++i)
        printf("%d ",fail[i]);
    return 0;
}

字典树，trie树

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int n;
struct node {
    int next[27];
    bool w;
} a[300000];
int tot;
bool flag[300000];

void build(char *b) {
    int p=0,len=strlen(b);
    for(int i=0; i<len; ++i) {
        int x=b[i]-'a';
        if(!a[p].next[x]) {
            a[p].next[x]=++tot;
        }
        p=a[p].next[x];
    }
    flag[p]=1;
}

void find(char *b) {
    int p=0,len=strlen(b);
    for(int i=0; i<len; ++i) {
        int x=b[i]-'a';
        if(!a[p].next[x]) {
            printf("NO\n");
            return;
        }
        p=a[p].next[x];
    }
    if(flag[p]) printf("YES\n");
    else printf("NO\n");
}

int main() {
    int n,m;
    char s[100];
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
        scanf("%s",s),build(s);
    scanf("%d",&m);
    while(m--)
        scanf("%s",s),find(s);
    return 0;
}

马拉车

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=11000007;
char s[maxn],S[maxn];
int p[maxn<<1];
int main()
{
    scanf("%s",s);
    S[0]='@';S[1]='#';
    int l=1,i=-1;
    while(s[++i]!='\0')
        S[++l]=s[i],S[++l]='#';
    int mx=0,id=0,ans=0;
    for(int i=1;i<=l;++i)
    {
        if(mx>i) p[i]=min(p[id*2-i],mx-i);//id*2-i即i-k
        else p[i]=1;
        while(S[i+p[i]]==S[i-p[i]]) p[i]++;
        if(mx<i+p[i]-1) mx=i+p[i]-1,id=i;
        ans=max(p[i]-1,ans);
    }
    printf("%d",ans);
    return 0;
}

AC自动机

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int N=2000100;
struct Tree{
    int fail,end; 
    int vis[27]; 
}e[N]; 

int cnt,n;
char s[N];

inline int read() {
    int n=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while (ch<='9'&&ch>='0') {n=n*10+ch-'0';ch=getchar();}
    return n*f;
}

inline void insert(char *s) {
    int n=strlen(s);
    int now=0;
    for(int i=0;i<n;++i) {
        int tmp=s[i]-'a';
        if(!e[now].vis[tmp]) e[now].vis[tmp]=++cnt;
        now=e[now].vis[tmp];
    }
    e[now].end++;
} 

inline void build() {
    queue<int> q;
    for(int i=0;i<26;++i)
        if(e[0].vis[i])
            q.push(e[0].vis[i]),e[e[0].vis[i]].fail=0;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=0;i<26;++i)
            if(e[u].vis[i]) {
                e[e[u].vis[i]].fail=e[e[u].fail].vis[i];
                q.push(e[u].vis[i]);    
            }
            else e[u].vis[i]=e[e[u].fail].vis[i];
    }
}

inline void query(char *s) {
    int l=strlen(s);
    int now=0,ans=0; 
    for(int i=0;i<l;++i) {
        int now=e[now].vis[s[i]-'a'];
        for(int t=now;t&&e[t].end!=-1;t=e[t].fail) {
            ans+=e[t].end;
            e[t].end=-1; 
        } 
    }
    printf("%d\n",ans); 
} 

int main() {
    n=read();
    for(int i=1;i<=n;++i) cin>>s,insert(s);
    build();
    cin>>s;
    query(s); 
    return 0; 
}