D – Searching the String (AC自动机)

  • 2019-02-09
  • 0
  • 0

题目链接:https://cn.vjudge.net/contest/281961#problem/D

题意:给出一个主串,和n个模式串,求模式串在主串中出现次数(允许覆盖或不允许覆盖)。

思路:新加一个last数组表示模式串在主串中上一次出现位置,如果这一次出现位置-上一次出现位置>=模式串长度就说明没有覆盖。

#include <bits/stdc++.h>

using namespace std;

char a[100005],b[25];
struct node
{
    node *next[26],*fail;
    int count,pos;
    int ans1,ans2;
    node()
    {
        fail=NULL;
        count=0;
        pos=0;
        ans1=ans2=0;
        for(int i=0; i<26; i++)
        {
            next[i]=NULL;
        }
    }
}*root,*q[1000005],*pos[100005];
int n;
int da[100005],len[100005],last[100005];

void init()
{
    root=new(node);
    memset(last,-1,sizeof(last));
}

struct node *insert(char *b,int pos)
{
    int n=strlen(b);
    node *p=root;
    for(int i=0; i<n; i++)
    {
        int ch=b[i]-'a';
        if(p->next[ch]==NULL)
        {
            p->next[ch]=new(node);
        }
        p=p->next[ch];
    }
    p->count++;
    p->pos=pos;
    return p;
}

void build_ac()
{
    int be,ed;
    be=0,ed=0;
    q[ed++]=root;
    while(be!=ed)
    {
        node *x=q[be];
        be++;
        for(int i=0; i<26; i++)
        {
            if(x->next[i]==NULL)
                continue;
            if(x==root)
                x->next[i]->fail=root;
            else
            {
                node *p=x->fail;
                while(p!=NULL)
                {
                    if(p->next[i]!=NULL)
                    {
                        x->next[i]->fail=p->next[i];
                        break;
                    }
                    p=p->fail;
                }
                if(p==NULL)
                    x->next[i]->fail=root;
            }
            q[ed++]=x->next[i];
        }
    }
}

void query()
{
    int n=strlen(a);
    node *p=root;
    for(int i=0; i<n; i++)
    {
        int ch=a[i]-'a';
        while(p!=root&&p->next[ch]==NULL)
        {
            p=p->fail;
        }
        p=p->next[ch];
        if(p==NULL)
            p=root;
        node *q=p;
        while(q!=root)
        {
            if(q->count>0)
            {
                int pos=q->pos;
                q->ans1++;
                if(last[pos]==-1||i-last[pos]>=len[pos])
                {
                    q->ans2++;
                    last[pos]=i;
                }
            }
            q=q->fail;
        }
    }
}

void dfs(node *x)
{
    if(x==NULL)return;
    for(int i=0;i<26;i++)
    {
        if(x->next[i]!=NULL)
        {
            dfs(x->next[i]);
        }
    }
    free(x);
}

int main()
{
    int kk=0;
    while(~scanf("%s",a))
    {
        scanf("%d",&n);
        init();
        for(int i=1; i<=n; i++)
        {
            scanf("%d %s",&da[i],b);
            pos[i]=insert(b,i);
            len[i]=strlen(b);
        }
        build_ac();
        query();
        printf("Case %d\n",++kk);
        for(int i=1; i<=n; i++)
        {
            int ans;
            if(da[i]==0)
                ans=pos[i]->ans1;
            else
                ans=pos[i]->ans2;
            printf("%d\n",ans);
        }
        printf("\n");
        dfs(root);
    }
    return 0;
}

评论

还没有任何评论,你来说两句吧