博客

又是数组开小。。。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
const int N=100005;
 
int n,m;
int ans[2000005];
int ch[2000005][30],tot,fail[2000005],last[2000005],to[N];
bool b[2000005];
 
void insert(char *s,int f)
{
    int len=strlen(s),now=0;
    for (int i=0;i<len;i++)
    {
        int id=s[i]-'a'; 
        if (ch[now][id]==0) ch[now][id]=++tot;
        now=ch[now][id];
    }
    b[now]=true;to[f]=now;
}
queue<int> q;
void getfail()
{
    for (int i=0;i<26;i++) if (ch[0][i]) q.push(ch[0][i]);
     
    while (!q.empty())
    {
        int u=q.front(),v,f;q.pop();
        for (int i=0;i<26;i++)
        if (v=ch[u][i])
        {
            f=fail[u];
            while (f&&ch[f][i]==0) f=fail[f];
            fail[v]=ch[f][i];
            if (b[fail[v]]) last[v]=fail[v];else last[v]=last[fail[v]];
            q.push(v);
        }
    }
}
queue<int> Q;
void updata(int i)
{
    while (i)
    {
        if (b[i]) b[i]=false,ans[i]++,Q.push(i);
        i=last[i];
    }
}
void work(char *s)
{
    int len=strlen(s),now=0,v;
    for (int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        while (ch[now][id]==0&&now) now=fail[now];
        now=ch[now][id];
        updata(now);
    }
    while (!Q.empty()) b[Q.front()]=true,Q.pop();
}
char ss[2000005];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%s",ss),insert(ss,i);
    getfail();
    scanf("%d",&m);
    for (int opt,x,i=1;i<=m;i++)
    {
        scanf("%d",&opt);
        if (opt==2) scanf("%d",&x),printf("%d\n",ans[to[x]]);
        else scanf("%s",ss),work(ss);
    }
    return 0;
}