Searching the String – ZOJ 3228 – AC自动机

来源: Searching the String – ZOJ 3228 – Virtual Judge

题目大意:给你一个主串和n个字串,每个子串前有一个数字,若为0输出这个字串在主串中出现的次数(可重叠),否则输出这个字串在主串中出现的次数(不可重叠)。
解题思路:可重叠的是一个非常常见的AC自动机求出现次数的题,详情可见洛谷 P3796 【模板】AC自动机(加强版),但这道题还要求求出不可重叠的次数,那么就在树上加一个变量pos代表上次匹配到这里时主串的位置,若当前位置减去存的pos大于等于字串长度的话计数器++。
代码

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

int n;
char p[100010],pp[100010];
int cnt=0;

struct node
{
    int fail,vis[26],id[2],len=0,pos=-1;
    int endd;
} ac[1000010];

int *y[100010];

void build(int d,int ii)
{
    int now=0;
    int l=strlen(p);
    for(int i=0; i<l; i++)
    {
        if(ac[now].vis[p[i]-'a']==0)
        {
            ac[now].vis[p[i]-'a']=++cnt;
            for(int j=0; j<26; j++)
            {
                ac[ac[now].vis[p[i]-'a']].vis[j]=0;
            }
            ac[ac[now].vis[p[i]-'a']].fail=0;
            ac[ac[now].vis[p[i]-'a']].endd=0;
            ac[ac[now].vis[p[i]-'a']].len=0;
            ac[ac[now].vis[p[i]-'a']].pos=-1;
            ac[ac[now].vis[p[i]-'a']].id[0]=
            ac[ac[now].vis[p[i]-'a']].id[1]=0;
        }
        now=ac[now].vis[p[i]-'a'];
    }
    ac[now].endd++;
    ac[now].len=l;
    y[ii]=&ac[now].id[d];
}

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

void ac_ans()
{
    int l=strlen(pp);
    int now=0;
    for(int i=0; i<l; i++)
    {
        //int k=pp[i]-'a'
        now=ac[now].vis[pp[i]-'a'];
        for(int t=now; t; t=ac[t].fail)
        {
            ac[t].id[0]++;
            if(ac[t].pos==-1||i-ac[t].pos>=ac[t].len)
            {
                ac[t].id[1]++;
                ac[t].pos=i;
            }
        }
    }
}

int main()
{
    //ios::sync_with_stdio(false);
    int kkk=0;
    while(~scanf("%s",pp))
    {
        kkk++;
        int now=0;
        for(int j=0; j<26; j++)
        {
            ac[now].vis[j]=0;
        }
        ac[now].fail=0;
        ac[now].endd=0;
        ac[now].len=0;
        ac[now].pos=-1;
        scanf("%d",&n);
        cnt=0;
        int d;
        for(int i=0; i<n; i++)
        {
            scanf("%d%s",&d,p);
            build(d,i);
        }
        ac[0].fail=0;
        getfail();
        ac_ans();
        printf("Case %d\n",kkk);
        for(int i=0; i<n; i++)
        {
            printf("%d\n",(*y[i]));
        }
        printf("\n");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注