POJ 1625 Censored!（AC自动机->指针版+DP+大数）题解

题目：给你n个字母，p个模式串，要你写一个长度为m的串，要求这个串不能包含模式串，问你这样的串最多能写几个

思路：dp+AC自动机应该能看出来，万万没想到这题还要加大数...orz

状态转移方程dp[i + 1][j->next] += dp[i][j]，其他思路和上一题hdu2457一样的，就是在AC自动机里跑就行了，不要遇到模式串结尾，然后最后把所有结尾求和就是答案。

注意下题目说给最多给50个字符且ASCII码大于32但是没说多大，直接开100多会RE，这里用map假装离散化一下。

参考：

代码：

#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
const int maxn = 1000+5;
const int maxm = 100000+5;
const int MOD = 1e7;
const int INF = 0x3f3f3f3f;
const int kind = 55;
const char baset = 0;
using namespace std;

/**********大数模板-start************/
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("\n");
    }
    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;
    }
    bool operator == (const BigInteger& B){
        for(int i = 0;i < 25;i++)
            if(A[i] != B[i]) return false;
        return true;
    }
    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;
    }
};
/**********大数模板-end************/

struct Trie{
    Trie *next[kind];
    Trie *fail;
    int flag;
    int id;
};
Trie *root,point[maxn];
queue<Trie*> Q;
map<char,int> mp;
int head,tail,idx;
char cha[1005];
int ID(char ch){
    return mp[ch];
}
Trie* NewNode(){
    Trie *temp = &point[idx];
    memset(temp ->next,NULL,sizeof(temp ->next));
    temp ->flag = 0;
    temp ->id = idx++;
    temp ->fail = NULL;
    return temp;
}

void Insert(char *s){
    Trie *p = root;
    for(int i = 0;s[i];i++){
        int x = ID(s[i]);
        if(p ->next[x] == NULL){
            p ->next[x] = NewNode();
        }
        p = p ->next[x];
    }
    p ->flag = 1;
}
void buildFail(){
    while(!Q.empty()) Q.pop();
    Q.push(root);
    Trie *p,*temp;
    while(!Q.empty()){
        temp = Q.front();
        Q.pop();
        for(int i = 0;i < kind;i++){
            if(temp ->next[i]){
                if(temp == root){
                    temp ->next[i] ->fail = root;
                }
                else{
                    p = temp ->fail;
                    while(p){
                        if(p ->next[i]){
                            temp ->next[i] ->fail = p ->next[i];
                            break;
                        }
                        p = p ->fail;
                    }
                    if(p == NULL) temp ->next[i] ->fail = root;
                }
                if(temp ->next[i] ->fail ->flag)
                    temp ->next[i] ->flag = 1;
                Q.push(temp ->next[i]);
            }
            else if(temp == root)
                temp ->next[i] = root;
            else
                temp ->next[i] = temp ->fail ->next[i];
        }
    }
}
BigInteger dp[55][150];    //主串第i位，AC自动机第j个
void solve(int n,int len){
    BigInteger zero;
    zero.set(0);
    for(int i = 0;i < idx;i++)
        dp[0][i].set(0);
    dp[0][0].set(1);
    for(int i = 1;i <= len;i++){
        for(int j = 0;j < idx;j++){
            if(point[j].flag) continue;
            if(dp[i - 1][j] == zero) continue;
            for(int k = 0;k < n;k++){
                int r = point[j].next[k] ->id;
                if(point[r].flag) continue;
                dp[i][r] = dp[i][r] + dp[i - 1][j];
            }
        }
    }
    BigInteger ans;
    ans.set(0);
    for(int i = 0;i < idx;i++){
        ans = ans + dp[len][i];
    }
    ans.print();
}

int main(){
    int n,m,p,Case = 1;
    while(scanf("%d%d%d",&n,&m,&p) != EOF){
        idx = 0;
        root = NewNode();
        scanf("%s",cha);
        for(int i = 0;i < n;i++){
            mp[cha[i]] = i;
        }
        for(int i = 0;i < p;i++){
            scanf("%s",cha);
            Insert(cha);
        }
        buildFail();
        solve(n,m);
    }
    return 0;
}

巴特西

POJ 1625 Censored!（AC自动机->指针版+DP+大数）题解

最新文章

热门文章