poj-1625 Censored![ac自动机+dp+高精度]

题目地址
先把病毒串丢进ac自动机里面。
dp[i][j]表示长度为i的从trie图的根节点到j满足条件的串的数量。
因为答案很大，要用到高精度。
注意的是建图的时候，ed[u] |= ed[f[u]]，如果失配指针的位置是病毒的话那么u也不能匹配。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 1e5+5;
struct BigInter {
private:
    int num[50], len;
    int base;
public:     
    BigInter() {
        memset(num,0,sizeof(num));
        len = 1;
        base = 10000;
     }
    BigInter(int v) {
        memset(num,0,sizeof(num));
        base = 10000;
        len = 0;
        do {
        	num[++len] = v%base;
        	v /= base;
        }while(v);
    }
    BigInter operator=(int x) {
         return *this = BigInter(x);
    }
    BigInter operator=(long long x) {
         return *this = BigInter(x);
    }
    BigInter operator+(BigInter &b) {
         BigInter res;
         res.len = max(this->len, b.len);
         for(int i = 1; i <= res.len; i++) {
             res.num[i] += this->num[i] + b.num[i];
             res.num[i+1] += res.num[i]/base;
             res.num[i] = res.num[i]%base;
         }
         if(res.num[res.len+1]) res.len++;
         return res;
    }
     BigInter operator+(long long x) {
	     BigInter res;
	     BigInter b = BigInter(x);
	     res.len = max(this->len, b.len);
	     for(int i = 1; i <= res.len; i++) {
	         res.num[i] += this->num[i] + b.num[i];
	         res.num[i+1] += res.num[i]/base;
	         res.num[i] = res.num[i]%base;
	     }
	     if(res.num[res.len+1]) res.len++;
	     return res;
     }
     BigInter operator*(BigInter &b) {
        BigInter res;
        res.len = this->len+b.len;
        for(int i = 1; i <= this->len; i++) {
            for(int j = 1; j <= b.len; j++) {
            	res.num[j+i-1] += this->num[i] * b.num[j];
            	res.num[j+i] += res.num[j+i-1]/base;
            	res.num[j+i-1] %= base;
            }
        }
        while(!res.num[res.len]) res.len--;
        return res;
     }
     BigInter operator*(long long x) {
        BigInter res;
        BigInter b(x);
        res.len = this->len+b.len;
        for(int i = 1; i <= this->len; i++) {
            for(int j = 1; j <= b.len; j++) {
            	res.num[j+i-1] += this->num[i] * b.num[j];
            	res.num[j+i] += res.num[j+i-1]/base;
            	res.num[j+i-1] %= base;
            }
        }
        while(!res.num[res.len]) res.len--;
        return res;
     }
     void operator +=(BigInter &b) {
         *this = *this + b;
     }
     void operator *=(BigInter &b) {
         *this = *this * b;
     }
     void operator +=(long long x) {
         BigInter b = BigInter(x);
         *this = *this + b;
     }
     void operator *=(long long x) {
     	BigInter b = BigInter(x);
         *this = *this * b;
     }
     BigInter operator++() {
     	*this = *this+1;
     	return *this;
     }
     BigInter operator ++(int) {
     	BigInter old = *this;
     	++(*this);
     	return old;
     }
     void print() {
         printf("%d", num[len]);
         for(int i = len-1; i >= 1; i--) {
         	printf("%04d", this->num[i]);
         }
         puts("");
     }
}dp[105][305];
int indx[5005];
struct node{
	int nex[maxn][305], tot, root;
	int f[maxn], ed[maxn];
	int newnode() {
		for(int i = 0; i < 300; i++) {
			nex[tot][i] = -1;
		}
		ed[tot] = 0;
		return tot++;
	}
	void init() {
		tot = 0;
		root = newnode();
	}
	void insert(char *s) {
		int len = strlen(s), u = root;
		for(int i = 0; i < len; i++) {
			int ch = indx[s[i]+100];
			if(nex[u][ch] == -1) nex[u][ch] = newnode();
			u = nex[u][ch];
		}
		ed[u] = 1;
	}
	void getfail() {
		queue<int>Q;f[root] = root;
		for(int i = 0; i < 300; i++) {
			if(nex[root][i] == -1) nex[root][i] = root;
			else {
				f[nex[root][i]] = root;
				Q.push(nex[root][i]);
			}
		}
		while(!Q.empty()) {
			int u = Q.front();Q.pop();
			ed[u] |= ed[f[u]];
			for(int i = 0; i < 300; i++) {
				if(nex[u][i] == -1) nex[u][i] = nex[f[u]][i];
				else {
					f[nex[u][i]] = nex[f[u]][i];
					Q.push(nex[u][i]);
				}
			}
		}
	}
	void query(int m, int n) {
		dp[0][0] = 1;
		for(int i = 1; i <= m; i++) {
			for(int j = 0; j < tot; j++) {
				if(ed[j] == 1) continue;
				for(int k = 0; k < n; k++) {
					if(ed[nex[j][k]] != 1) {
						dp[i][nex[j][k]] += dp[i-1][j];
					}
				}
			}
		}
		BigInter res;
		for(int i = 0; i < tot; i++) res = res + dp[m][i];
		res.print();
	}
}ac;
char ss[maxn];
int main() {
	int n, m, p;
	scanf("%d%d%d", &n, &m, &p);
	scanf("%s", ss);
	ac.init();
	int len = strlen(ss);
	for(int i = 0; i < len; i++) indx[ss[i]+100] = i;
	for(int i = 1; i <= p; i++) {
		scanf("%s", ss);
		ac.insert(ss);
	}
	ac.getfail();
	ac.query(m, n);
}