ZOJ 3228 AC自动机

题意

给一些字符串，后面跟一个数字。如果0的话，就允许统计层叠的的字符串个数。如果1的话，就只能统计不层叠的字符串个数。要求输出统计个数

题解

实现起来最简单的方式，也是大家用的最多的方式就是用一个AC自动机，然后在统计的时候，开两个数组分别统计允许层叠的个数和不允许层叠的个数。最后需要输出哪种类型的个数，就直接输出就可以了。

代码

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<string>
#define UP(i,l,h) for(int i=l;i<h;i++)
#define DOWN(i,h,l) for(int i=h-1;i>=l;i--)
#define W(a) while(a)
#define MEM(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
#define MAXN 100010
#define MOD 1000000007
#define EPS 1e-10

using namespace std;

char tar[100010];
int mp[100010],tp[100010];
int val[600010],f[600010],last[600010],cnt[600010][2],pos[600010];
char st[15];
int ch[600010][26];
int sz;

void insert(int i) {
    int len=strlen(st);
    int u=0;
    UP(i,0,len) {
        int x=st[i]-'a';
        if(!ch[u][x]) {
            ch[u][x]=sz++;
        }
        u=ch[u][x];
    }
    val[u]=len;
    mp[i]=u;
// cout<<val[u]<<" "<<u<<endl;
}

void getFail() {
    MEM(f,0);
    MEM(last,0);
    queue<int> q;
    UP(i,0,26) {
        int x=ch[0][i];
        if(x) {
            q.push(x);
        }
    }
    W(!q.empty()) {
        int r=q.front();
        q.pop();
        UP(i,0,26) {
            int x=ch[r][i];
            if(!x) {
                ch[r][i]=ch[f[r]][i];
                continue;
            }
            q.push(x);
            int v=f[r];
            f[x]=ch[v][i];
            last[x]=val[f[x]]>0?f[x]:last[f[x]];
        }
    }
}

void solve(int u,int p) {
    if(u!=0) {
        cnt[u][0]++;
        if(pos[u]==-1||(pos[u]+val[u])<=p) {
            cnt[u][1]++;
            pos[u]=p;
        }
        solve(last[u],p);
    }
}

void find() {
    int len=strlen(tar);
    int u=0;
    UP(i,0,len) {
        int x=tar[i]-'a';
        u=ch[u][x];
        if(val[u])
            solve(u,i);
        else if(last[u])
            solve(last[u],i);
    }
}

int main() {
    int ks=1;
    W(~scanf("%s",tar)) {
        MEM(ch,0);
        MEM(val,0);
        MEM(cnt,0);
        MEM(pos,-1);
        MEM(mp,0);
        MEM(tp,0);
        sz=1;
        int n;
        scanf("%d",&n);
        UP(i,0,n) {
            scanf("%d%s",&tp[i],st);
            insert(i);
        }
        getFail();
        find();
        printf("Case %d\n",ks++);
        UP(i,0,n) {
            printf("%d\n",cnt[mp[i]][tp[i]]);
        }
        puts("");
    }
}