poj--1625Censored!+AC 로봇의 dp+ 대수

제목 링크: 입력을 클릭하면 매트릭스로 충분히 할 수 있을 것 같지만 큰 숫자를 사용해서 메모리가 켜지지 않아서 dp로 썼습니다.사실 dp의 과정은 우리가 단어 출현을 금지하는trie로 m보를 걷는 과정이다.우리는 dp[i][j]가 i보를 지나 노드 j에 도달하는 방안수를 정의했다. 그러면 상태 이동은 dp[i][j]=sum(dp[i-1][k])이어야 한다. 그 중에서 k는 j의 노드에 도달할 수 있고 바이러스 노드가 될 수 없다는 것을 의미한다.그러나 사실 이런 코드는 그렇게 쓰기 쉽지 않다. 사실 우리는 노드 j로 주동적으로 그의 하위 노드 k를 업데이트할 수 있다. 이렇게 전이 방정식은 dp[i][next[j][k]]]]+=dp[i-1][j]가 된다.nxt[j][k]가 바이러스 노드를 사용할 수 없도록 요구합니다.총괄적으로 말하면 AC 자동기의 dp는 우리가 세운trie 트리와 위의 이동 방식을 이용하여 상태 이동을 하는 것이다.
코드는 다음과 같습니다.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

///    
struct BigInteger{
    int A[25];
    enum{MOD = 10000};
    BigInteger(){memset(A, 0, sizeof(A)); A[0]=1;}
    void set(int x){memset(A, 0, sizeof(A)); A[0]=1; A[1]=x;}
    void print(){
        printf("%d", A[A[0]]);
        for (int i=A[0]-1; i>0; i--){
            if (A[i]==0){printf("0000"); continue;}
            for (int k=10; k*A[i]<MOD; k*=10) printf("0");
            printf("%d", A[i]);
        }
        printf("
");
    }
    int& operator [] (int p) {return A[p];}
    const int& operator [] (int p) const {return A[p];}
    BigInteger operator + (const BigInteger& B){
        BigInteger C;
        C[0]=max(A[0], B[0]);
        for (int i=1; i<=C[0]; i++)
            C[i]+=A[i]+B[i], C[i+1]+=C[i]/MOD, C[i]%=MOD;
        if (C[C[0]+1] > 0) C[0]++;
        return C;
    }
    BigInteger operator * (const BigInteger& B){
        BigInteger C;
        C[0]=A[0]+B[0];
        for (int i=1; i<=A[0]; i++)
            for (int j=1; j<=B[0]; j++){
                C[i+j-1]+=A[i]*B[j], C[i+j]+=C[i+j-1]/MOD, C[i+j-1]%=MOD;
            }
        if (C[C[0]] == 0) C[0]--;
        return C;
    }
}One;

const int maxn=10*10+5;
char alph[maxn];
map<char,int>h;

int getIndex(char ch)
{
     return h[ch];
}

struct Trie
{
    int next[maxn][maxn/2],fail[maxn],flag[maxn];
    int root,L,len;
    int newnode()
    {
        memset(next[L],-1,sizeof(next[L]));
        flag[L++];
        return L-1;
    }
    void init()
    {
        L=0;
        root=newnode();
    }
    void insert(char buf[])
    {
        int len1=strlen(buf);
        int now=root;
        for(int i=0;i<len1;i++)
        {
            int index=getIndex(buf[i]);
            if(next[now][index]==-1)
               next[now][index]=newnode();
            now=next[now][index];
        }
        flag[now]=1;
    }
    void build()
    {
        queue<int>Q;
        fail[root]=root;
        for(int i=0;i<len;i++)
        {
          if(next[root][i]==-1)
             next[root][i]=root;
          else
          {
              fail[next[root][i]]=root;
              Q.push(next[root][i]);
          }
        }
        while(!Q.empty())
        {
            int now=Q.front();
            if(flag[fail[now]])
               flag[now]++;
            Q.pop();
            for(int i=0;i<len;i++)
            {
                if(next[now][i]==-1)
                  next[now][i]=next[fail[now]][i];
                else
                {
                    fail[next[now][i]]=next[fail[now]][i];
                    //flag[next[now][i]]|=flag[next[fail[now]][i]];
                    Q.push(next[now][i]);
                }
            }
        }
    }
};


Trie ac;
char str[maxn];

BigInteger dp[maxn][maxn];

int main()
{
    int n,m,p;
    ///freopen("in.txt","r",stdin);
    One.set(1);
    while(scanf("%d%d%d",&n,&m,&p)!=EOF)
    {
        h.clear();
        scanf("%s",alph);
        for(int i=0;i<strlen(alph);i++)
           h[alph[i]]=i;
        ac.init();
        ac.len=strlen(alph);
        for(int i=0;i<p;i++)
        {
            scanf("%s",str);
            ac.insert(str);
        }
        ac.build();
        for(int i=0;i<=m;i++)
          for(int j=0;j<ac.L;j++)
             dp[i][j].set(0);
        dp[0][0].set(1);
        for(int i=1;i<=m;i++)
          for(int j=0;j<ac.L;j++)
            for(int k=0;k<n;k++)
            {
                if(ac.flag[ac.next[j][k]]) continue;
                dp[i][ac.next[j][k]]=dp[i][ac.next[j][k]]+dp[i-1][j];
            }
        BigInteger ans;
        ans.set(0);
        for(int i=0;i<ac.L;i++)
          ans=ans+dp[m][i];
        ans.print();
    }
  return 0;
}