传送门
dp没怎么理解好。。。QAQ
f[i][j]表示长度为i，当前节点为j的方案数
——代码
#include <queue> #include <cstdio> #include <cstring> #define N 100001 #define p 10007 int n, m, cnt, ans, sum = 1; int next[N][26], fail[N], f[101][N]; bool val[N]; char s[N]; std::queue <int> q; inline void insert() val[now] = 1; } inline void make_fail() fail[next[now][i]] = next[fail[now]][i]; val[next[now][i]] |= val[next[fail[now]][i]]; q.push(next[now][i]); } } } int main() make_fail(); for(i = 1; i <= m; i++) sum = (sum * 26) % p; f[0][0] = 1; for(i = 1; i <= m; i++) for(j = 0; j <= cnt; j++) for(i = 0; i <= cnt; i++) if(!val[i]) ans = (ans + f[m][i]) % p; printf("%d\n", ((sum ans) % p + p) % p); return 0; }
上一篇：后缀数组
下一篇：[POJ1226]Substrings（后缀数组）
AC自动机 DP
