poj2778 ac自动机+矩阵快速幂

时间：2022-12-09 14:51:27

给m个子串，求长度为n的不包含子串的母串数，最直接的应该是暴搜，肯定tle，考虑用ac自动机

将子串建成字典树，通过next表来构造矩阵，然后用矩阵快速幂求长度为n的数量

邻接矩阵https://wenku.baidu.com/view/d7b9787f1711cc7931b716b0.html

对于a(i,j)^k  是指从i到j经过k个点的所有情况数

注意对于End数组，如果某个节点如果fail指针End数组为1，那么End【该节点】也是1

string要开全局变量，不然不能运行= =

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<stack>

#include<vector>

#include<cstdio>

#include<iomanip>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pii pair<int,int>

#define C 0.5772156649

#define pi acos(-1.0)

#define ll long long

#define mod 100000

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f;

struct Node{

    int len;

    ll a[N][N];

};

Node mul(Node x,Node y)

{

    Node ans;

    ans.len=x.len;

    memset(ans.a,,sizeof ans.a);

    for(int i=;i<x.len;i++)

        for(int j=;j<x.len;j++)

            for(int k=;k<y.len;k++)

                ans.a[i][k]=(ans.a[i][k]+x.a[i][j]*y.a[j][k])%mod;

    return ans;

}

Node quick_mul(Node x,int n)

{

    Node ans;

    ans.len=x.len;

    memset(ans.a,,sizeof ans.a);

    for(int i=;i<ans.len;i++)ans.a[i][i]=;

    while(n)

    {

        if(n&)ans=mul(ans,x);

        x=mul(x,x);

        n/=;

    }

    return ans;

}

struct Trie{

    int tot,root;

    int Next[N][],fail[N];

    bool End[N];

    int change(char s)

    {

        if(s=='A')return ;

        else if(s=='C')return ;

        else if(s=='T')return ;

        else return ;

    }

    int newnode()

    {

        for(int i=;i<;i++)

            Next[tot][i]=-;

        End[tot]=;

        return tot++;

    }

    void init()

    {

        tot=;

        root=newnode();

    }

    void insertstring(string s)

    {

        int now=root;

        for(int i=;i<s.size();i++)

        {

            if(Next[now][change(s[i])]==-)

                Next[now][change(s[i])]=newnode();

            now=Next[now][change(s[i])];

        }

        End[now]=;

    }

    void build()

    {

        queue<int>q;

        fail[root]=root;

        for(int i=;i<;i++)

        {

            if(Next[root][i]==-)Next[root][i]=root;

            else

            {

                fail[Next[root][i]]=root;

                q.push(Next[root][i]);

            }

        }

        while(!q.empty())

        {

            int now=q.front();

            q.pop();

            if(End[fail[now]])End[now]=;

            for(int i=;i<;i++)

            {

                if(Next[now][i]==-)Next[now][i]=Next[fail[now]][i];

                else

                {

                    fail[Next[now][i]]=Next[fail[now]][i];

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

                }

            }

        }

    }

    int solve(int n)

    {

        Node ans;

        ans.len=tot;

        memset(ans.a,,sizeof ans.a);

        for(int i=;i<tot;i++)

            for(int j=;j<;j++)

                if(!End[Next[i][j]])

                    ans.a[i][Next[i][j]]++;

        ans=quick_mul(ans,n);

        int res=;

        for(int i=;i<ans.len;i++)

            res=(res+(int)ans.a[][i])%mod;

        return res;

    }

};

Trie ac;

string s;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n,m;

    while(cin>>m>>n)

    {

        ac.init();

        for(int i=;i<m;i++)

        {

            cin>>s;

            ac.insertstring(s);

        }

        ac.build();

        cout<<ac.solve(n)<<endl;

    }

    return ;

}

/********************

********************/

相关文章