2017多校第6场 HDU 6096 String AC自动机

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6096

题意：给了一些模式串，然后再给出一些文本串的不想交的前后缀，问文本串在模式串的出现次数。

解法：

因为要求前缀后缀都包含的个数，所以可以把字符串a转换成a#a这样一个字符串，比如abca就转换成abca#abca

然后对于一组前缀a后缀b转换成b{a,比如ab ca,就是ca{ab，

然后对前缀后缀的串建立AC自动机，让主串去匹配，如上述例子，ca{ab满足为abca{abca的一个子串，也就是abca满足这个前缀后缀，所以问题，就转换成了典型的ac自动机匹配问题。

加个{的原因是为了只让后缀{前缀这种串能在AC自动机匹配到。

然后求答案的时候，需要对连接到自己的fail的位置累加一下，含义想一下就明白了。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000010;

const int maxs = 30;

string s[maxn];

int d[maxn],pos[maxn],ans[maxn],st[maxn],len[maxn];

struct Acautomata{

    int nxt[maxn][maxs],cnt[maxn],fail[maxn],match[maxn],dep[maxn];

    int L, root;

    int newnode(){

        for(int i=0; i<maxs; i++) nxt[L][i]=-1;

        cnt[L++]=0;

        fail[L-1]=0;

        return L-1;

    }

    void init(){

        L = 0;

        root = newnode();

    }

    int Insert(string a){

        int now=root;

        for(int i=0; a[i]; i++){

            if(nxt[now][a[i]-'a']==-1){

                nxt[now][a[i]-'a']=newnode();

                dep[L-1]=i+1;

            }

            now=nxt[now][a[i]-'a'];

        }

        cnt[now]=1;

        return now;

    }

    void build()

    {

        queue<int>q;

        int now=root;

        fail[0] = 0;

        for(int i=0; i<maxs; i++){

            if(nxt[now][i]==-1){

                nxt[now][i]=root;

                continue;

            }

            else{

                fail[nxt[now][i]]=root;

                q.push(nxt[now][i]);

            }

        }

        while(!q.empty())

        {

            now = q.front();

            q.pop();

            for(int i=0; i<maxs; i++){

                if(nxt[now][i]!=-1){

                    q.push(nxt[now][i]);

                    fail[nxt[now][i]] = nxt[fail[now]][i];

                    match[nxt[now][i]] = cnt[nxt[now][i]]?nxt[now][i]:match[nxt[fail[now]][i]];

                }else{

                    nxt[now][i] = nxt[fail[now]][i];

                }

            }

        }

    }

    void solve1(string a, int h){

        int now=root;

        int sz = a.size();

        for(int i=0; i<sz; i++){

            now=nxt[now][a[i]-'a'];

            while(dep[now]>h){

                now=fail[now];

            }

            ans[match[now]]++;

        }

    }

    void solve2(){//累加答案，对连到自己的fail进行累加求和

        memset(d, 0, sizeof(d));

        int j, k = 0;

        for(int i=0; i<L; i++) d[fail[i]]++;

        for(int i=0; i<L; i++) if(!d[i]) st[k++]=i;

        for(int i=0; i<k; i++){

            j=fail[st[i]];

            ans[j]+=ans[st[i]];

            if(!(--d[j])){

                st[k++]=j;

            }

        }

    }

}ZXY;

int n, q;

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        ZXY.init();

        scanf("%d%d", &n,&q);

        for(int i=0; i<n; i++){

            cin>>s[i];

            len[i] = s[i].size()+1;

            string temp=s[i];

            s[i]+=char('z'+1);

            s[i]+=temp;

        }

        for(int i=0; i<q; i++){

            string s1,s2;

            cin>>s1>>s2;

            s2 = s2 + char('z'+1);

            s2 = s2 + s1;

            pos[i] = ZXY.Insert(s2);

        }

        ZXY.build();

        for(int i=0; i<n; i++){

            ZXY.solve1(s[i],len[i]);

        }

        ZXY.solve2();

        for(int i=0; i<q; i++) printf("%d\n", ans[pos[i]]);

        for(int i=0; i<=ZXY.L; i++){

            ans[i]=0;

            ZXY.match[i]=0;

        }

    }

    return 0;

}

巴特西

2017多校第6场 HDU 6096 String AC自动机

最新文章

热门文章