字符串

KMP

    scanf("%s%s", b+1, a+1);
    int n = strlen(a+1), m = strlen(b+1);
    for(int i=2, l=0; i<=n; i++)
    {
        while(l&&a[i]!=a[l+1]) l=nxt[l];
        if(a[i]==a[l+1]) l++;
        nxt[i] = l;
    }
    int no = 1;
    for(int i=1, l=0; i<=m; i++)
    {
        while(l&&b[i]!=a[l+1]) l=nxt[l];
        if(b[i]==a[l+1]) l++;
        if(l==n) no=0, printf("%d\n", i-l+1);
    }
    if(no) printf("NO");

AC automata

#include<bits/stdc++.h>
using namespace std;

const int N = 50*10010;
const int ARTICLE = 1000010;

class AcAuto
{
    int tr[N][26], val[N], fail[N], last[N];
    int tot;
public: 
    inline void init()
    {
        memset(tr[0],0,sizeof tr[0]);
    }
    void insert(char* s)
    {
        int p=0, len=strlen(s);
        for(int i=0; i<len; i++)
        {
            int&v = tr[p][s[i]-'a'];
            if(!v) v=++tot, memset(tr[tot], 0, sizeof tr[0]), val[tot]=0;
            p=v;
        }
        val[p]++;
    }
    int find(char *s)
    {
        int p=0, len=strlen(s), ans=0;
        for(int i=0; i<len; i++)
        {
            p = tr[p][s[i]-'a'];
            for(int j=val[p]?p:last[p]?last[p]:0; j; j=last[j])
                ans+=val[j], val[j]=0;
        }
        return ans;
    }
    void calcFails()
    {
        static queue<int> q;
        for(int c=0; c<26; c++)
        {
            int v = tr[0][c];
            if(v) q.push(v), fail[v]=last[v] = 0;
        }
        while(!q.empty())
        {
            int u = q.front(); q.pop();
            for(int c=0; c<26; c++)
            {
                int&v = tr[u][c];
                if(v)
                {
                    q.push(v);
                    int uf = fail[u];
                    while(uf && !tr[uf][c]) uf = fail[uf];
                    int vf = fail[v] = tr[uf][c];
                    last[v] = val[vf] ? vf : last[vf];
                }
                else v = tr[fail[u]][c];    
            }
        }
    }
}acAuto;

char mod[60], article[ARTICLE];
int n;

signed main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        acAuto.init();
        scanf("%d", &n);
        while(n--)
        {
            scanf("%s", mod);
            acAuto.insert(mod);
        }
        acAuto.calcFails();
        scanf("%s",article);
        int ans = acAuto.find(article);
        printf("%d\n", ans);
    }
    
}