链接:http://zerojudge.tw/ShowProblem?problemid=b179
思路仿照hh犇,table[i][j][k]表示第i次转移后长度为j所在节点为k的串的种数
分裂的基因直接用ch转移,而对于变短要分俩种情况讨论,当前长度小于等于所在节点的深度时使用fail指针转移(实际上当前长度小于节点深度这种情况是不存在的,所以只考虑等于的情况即可),这相当于把当前的串去掉首字母后再从树根查找所得到的节点位置,而且由于当前串不包含任何病态基因,所以这种转移是正确的,第二种是
当前串长度大于节点深度,这时只需要把长度-1即可,节点不用转变,因为当前串去掉首字母后仍然包含从树根到当前节点所生成的串
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <cstring> #include <stack> #include <cctype> #include <utility> #include <map> #include <string> #include <climits> #include <set> #include <string> #include <sstream> #include <utility> #include <ctime> using std::priority_queue; using std::vector; using std::swap; using std::stack; using std::sort; using std::max; using std::min; using std::pair; using std::map; using std::string; using std::cin; using std::cout; using std::set; using std::queue; using std::string; using std::istringstream; using std::make_pair; using std::getline; using std::greater; using std::endl; using std::multimap; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PAIR; typedef multimap<int, int> MMAP; const int MAXN(1510); const int SIGMA_SIZE(4); const int MAXM(110); const int MAXE(4000010); const int MAXH(18); const int INFI((INT_MAX-1) >> 2); const int MOD(10007); const ULL LIM(1000000000000000ull); struct AC { int ch[MAXN][SIGMA_SIZE]; int f[MAXN], dep[MAXN]; bool val[MAXN]; int size; void init() { memset(ch[0], 0, sizeof(ch[0])); f[0] = 0; val[0] = false; size = 1; } inline int idx(char temp) { return temp-'a'; } void insert(char *S) { int u = 0, id, td = 1; for(; *S; ++S, ++td) { id = idx(*S); if(!ch[u][id]) { memset(ch[size], 0, sizeof(ch[size])); val[size] = false; dep[size] = td; ch[u][id] = size++; } u = ch[u][id]; } val[u] = true; } int que[MAXN]; int front, back; void construct() { front = back = 0; int cur, u; for(int i = 0; i < SIGMA_SIZE; ++i) { u = ch[0][i]; if(u) { que[back++] = u; f[u] = 0; } } while(front < back) { cur = que[front++]; for(int i = 0; i < SIGMA_SIZE; ++i) { u = ch[cur][i]; if(u) { que[back++] = u; f[u] = ch[f[cur]][i]; val[u] |= val[f[u]]; } else ch[cur][i] = ch[f[cur]][i]; } } } }; AC ac; int table[2][110][MAXN]; char str[110], tstr[20]; void solve(int m) { int cur = 0, last = 1; memset(table[last], 0, sizeof(table[0])); int start = 0, id; int len = 0; for(char *pi = str; *pi; ++pi, ++len) { id = ac.idx(*pi); start = ac.ch[start][id]; if(ac.val[start]) { printf("0 1\n"); return ; } } table[last][len][start] = 1; int lim = min(100, m+len); int ans1 = 0, ans2 = 0; for(int i = 0; i < m; ++i) { memset(table[cur], 0, sizeof(table[cur])); for(int j = 1; j <= lim; ++j) for(int k = 0; k < ac.size; ++k) if(table[last][j][k] && !ac.val[k]) { for(int k2 = 0; k2 < SIGMA_SIZE; ++k2) table[cur][j+1][ac.ch[k][k2]] = (table[cur][j+1][ac.ch[k][k2]]+table[last][j][k])%MOD; if(j == ac.dep[k]) // 处理变短的情况, j < ac.dep[k]的情况不会发生 table[cur][j-1][ac.f[k]] = (table[cur][j-1][ac.f[k]]+table[last][j][k])%MOD; else if(j > ac.dep[k]) table[cur][j-1][k] = (table[cur][j-1][k]+table[last][j][k])%MOD; } for(int j = 0; j < ac.size; ++j) { ans1 = (ans1+table[cur][0][j])%MOD; if(ac.val[j]) { for(int k = 1; k <= lim; ++k) ans2 = (ans2+table[cur][k][j])%MOD; } } cur ^= 1; last ^= 1; } printf("%d %d\n", ans1, ans2); } int main() { while(~scanf("%s", str)) { int n, m; scanf("%d%d", &m, &n); ac.init(); for(int i = 0; i < n; ++i) { scanf("%s", tstr); ac.insert(tstr); } ac.construct(); solve(m); } return 0; }