[AC自动机]zoj 3228：Searching the String

大致题意：

    给出n组模式串数据，每组数据由一个01数字和一个模式串组成，再给出一个文本串。对于每组模式串数据，分别统计其在文本串中出现了多少次，如果前面的数字是0，则代表计数的时候可以重叠，如果是0则代表不能重叠。

 

大致思路：
    好麻烦的一道题，有思路但是真的很难敲，要用多个数组来控制好数据之间的关系，最后还狂mle……擦。对于可以重叠的，直接ac自动机即可，对于不能重叠的，求出当前的位置距离其上次匹配的距离再判断即可。

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
const int nMax=600002;
const int mMax=100002;
class node{
public:
    int id;
    int count,len;
    node *next[26],*fail;
    node(){
        id=-1;
        count=0;           //count用来记录当前这个节点的询问状态
        fail=NULL;
        for(int i=0;i<26;i++)next[i]=NULL;
    }
}*root,*que[nMax];
int cnt;
int insert(char *s,int d){    //构造前缀树
    int i;
    node *r=root;
    int l=strlen(s);
    for(i=0;i<l;i++){
        int loc=s[i]-'a';
        if(r->next[loc]==NULL){
            r->next[loc]=new node();
        }
        r=r->next[loc];
    }
    if(r->id==-1){
        r->id=cnt;
        cnt++;
    }
    r->len=l;
    r->count|=d;
    return r->id;
}

void acAuto(){      //用bfs为每个节点设定fail指针
    int i,head=0,tail=0;
    node *p,*tmp;
    root->fail=NULL;
    que[tail++]=root;
    while(head<tail){
        tmp=que[head++];
        for(i=0;i<26;i++){
            if(tmp->next[i]==NULL)continue;
            if(tmp==root){
                tmp->next[i]->fail=root;
            }
            else {
                for(p=tmp->fail;p!=NULL;p=p->fail){
                    if(p->next[i]!=NULL){
                        tmp->next[i]->fail=p->next[i];
                        break;
                    }
                }
                if(p==NULL){
                    tmp->next[i]->fail=root;
                }
            }
            que[tail++]=tmp->next[i];
        }
    }
}
int vis[nMax][2],last[nMax],type[mMax],loc[mMax];
char str[10],text[mMax];
void search(int n){
    int i,idx;
    node *p=root,*tmp;
    for(i=0;text[i];i++){
        idx=text[i]-'a';
        while(p->next[idx]==NULL&&p!=root){
            p=p->fail;
        }
        p=p->next[idx];
        if(p==NULL)p=root;
        for(tmp=p;tmp!=NULL;tmp=tmp->fail){//&&tmp->count!=-1   因为这里需要求的是该字符串出现的次数
            if(tmp->id!=-1){
                if(tmp->count&1){
                    vis[tmp->id][0]++;
                }
                if(tmp->count&2){
                    if(i-tmp->len+1>last[tmp->id]){
                        vis[tmp->id][1]++;
                        last[tmp->id]=i;
                    }
                }
            }
        }
    }
}

int main(){
    int n,i,j,flag,a,cas=0;
    while(scanf("%s",text)!=EOF){
        cas++;
        cnt=1;
        root=new node();
        memset(vis,0,sizeof(vis));
        memset(last,-1,sizeof(last));
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%d%s",&type[i],str);
            loc[i]=insert(str,type[i]+1);
        }
        acAuto();
        search(n);
        printf("Case %d\n",cas);
        int k;
        for(i=0;i<n; i++){
            if(type[i]==0){
                k=0;
            }else{
                k=1;
            }
            k=vis[loc[i]][k];
            printf("%d\n", k);
        }
        printf("\n");
    }
    return 0;
}