本文共 5026 字，大约阅读时间需要 16 分钟。
hdu 2222模板题，测试专用，测烂为止。
hdu 2896模板题。
hdu 3065水，查询稍微改一下貌似就OK
zoj 3430 需要解码……由于是个base64，所以解码需要用unsigned char 而且要算出解码的长度……某此月赛题，表示不会解码看shi个报告。
poj 2778 矩阵乘法，注意以自动机上的节点表示状态，每一个状态对应一个输入都会有下一状态（就是原来query里那么写的）。然后构建转移矩阵，用快速幂转移，略卡常数，模数很小，矩阵乘法中间不要取模。
hdu 2243 同样为矩阵乘法，模数为1 << 64直接用ULL 溢出就相当于取模了…… 1 + 26^1 ＋ …… + 26^n 减去不含字串的。sumpow写错了……调自动机调了好久……
poj 1625 简单自动机DP，恶心的是需要大数……
hdu 2825 状态压缩自动机DP，很好的题目，状态为[当前串长度，自动机上的状态，二进制表示包换那些字串]。卡常数，需要把所有自动机中的下一状态预先处理出来，每个状态含那些串也处理出来，注意转移顺序。才能AC
hdu 2296 最大值的字典序最小，高效的方式是把串都反过来，然后插入自动机从后向前转移。但是直接暴力用string保存转移的最小字典序性价比很高……
poj 3691 基础的自动机DP 入门推荐级别题目
hdu 3341 恶题……变进制hash 一下 然后DP，状态数最多11^4 * 自动机状态。出题人就不能给个小点的范围吗……状态表示为[A][C][T][G][自动机状态]ACTG表示对已字符的个数，这样就可以不用长度来表示了，然后最大是11^4，考虑极端情况40 0 0 0 不能开一个41 * 41 * 41 * 41*状态数的数组，所以用变进制压缩ACTG就可以了……
zoj 3228 对于不可重叠的字符串记录最后一次出现的位置即可。然后一次查询统计。
hdu 3247 如果以自动机位状态用BFS转移的话， 复杂度太高，所以我们换一种思路，对于每个字符串要包含的文本，如果是结尾的话，必定在自动机的固定的状态上，然后我们把root和n个文本的结尾作为节点bfs预处理两点间的最短路，然后问题就转化成了TSP问题了，复杂度将为(S(自动机状态) * (n + 1)) + (n + 1)^2 * 2^n的复杂度。可以秒杀之。
zeroonlinejudge的空罐问题。如果不用长度，只用自动机做状态，要把所有可能出现的字符串插入到自动机中4^100的状态，显然不行……（也就我这么蒟蒻，开始这么想），所以状态上要加上长度。
状态 dp[i][j][k]第i天长度为j在自动机k状态的个数。
增长的问题很水，就是用单纯的自动机转移，用goStatus做转移，对于字符串变短的就用fail转移，然后每个状态给一个深度，分类讨论一下：
当j == 1的时候减少，就是是回收的字符串增减。
如果j > k->depth ，那么状态k是不变的。因为在开始减少字符不会导致向fail转移，字符串的后缀还是在k状态。
j <= k->depth的话，就转移到k->fail的状态。
贴上最后这题的代码+我们的模板
#pragma comment(linker, "/STACK:16777216") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LEFT(i) ((i) << 1) #define RIGHT(i) (((i) << 1) | 1) #define MID(i) ((l[i] + r[i]) >> 1) #define CC(i, v) memset(i, v, sizeof(i)) #define REP(i, l, n) for(int i = l;i < int(n);++i) #define FOREACH(con, i) for(__typeof(con.begin()) i = con.begin();i != con.end();++i) #define DEBUG(i) cout << #i << " " << i << endl; #define lowbit(x) ((x) & (-x)) typedef long long LL; typedef unsigned long long ULL; #define code(ch) ((ch) - 'a') const int KIND = 4; const int MAXN = 1600; struct node { node* next[KIND], *fail; int count, depth; bool valid; } pool[MAXN], *pp, *root, *q[MAXN]; int head, tail; node *newNode() { pp->fail = NULL; pp->count = 0; pp->valid = true; memset(pp->next, 0, sizeof (pp->next)); return pp++; } void initialize() { pp = pool; root = newNode(); } node* insert(char *str) { node *now = root; while (*str) { int idx = code(*str); if (now->next[idx] == NULL) now->next[idx] = newNode(); now = now->next[idx]; str++; } now->count++; return now; } void buildFail(node* now, int ith)//build now's ith son { if(now == root) now->next[ith]->fail = root; node* tmp = now->fail; while(tmp) { if(tmp->next[ith] != NULL) { now->next[ith]->fail = tmp->next[ith]; return; } tmp = tmp->fail; } if(tmp == NULL) now->next[ith]->fail = root; } void build() { head = tail = 0; q[tail++] = root; while (head != tail) { node *beg = q[head++]; for (int i = 0; i < KIND; i++) { if (beg->next[i] == NULL) continue; buildFail(beg, i); q[tail++] = beg->next[i]; } } } bool reachEnd(node* now) { while(now != root) { if(now->count) return true; now = now->fail; } return false; } node* goStatus(node* now, int ith) { while(now->next[ith] == NULL && now != root) now = now->fail; now = now->next[ith]; return now == NULL ? root : now; } void calDepth(node* now, int depth) { if(now == NULL) return; now->depth = depth; for(int i = 0; i < KIND; i++) calDepth(now->next[i], depth + 1); } const int N = 105; const int MOD = 10007; char str[N], nowStr[N]; int dp[2][N + 1][MAXN]; void add(int& now, int ad) { now += ad; if(now >= MOD) now -= MOD; } pair DP(char* nowStr, int day, int n) { node* now = root; memset(dp, 0, sizeof(dp)); for(int i = 0; nowStr[i]; i++) { now = goStatus(now, code(nowStr[i])); if(reachEnd(now)) return make_pair(0, 1); } dp[0][strlen(nowStr)][now - pool] = 1; int ans1 = 0, ans2 = 0; for(int i = 0; i < day; i++) { memset(dp[1], 0, sizeof(dp[1])); for(int j = 1; j < N; j++) { for(node* k = pool; k < pp; k++) { int s = k - pool; if(dp[0][j][s] == 0) continue; //fail转移，字符串变短 if(j == 1) add(ans1, dp[0][j][s]); else if(j <= k->depth) add(dp[1][j - 1][k->fail - pool], dp[0][j][s]); else add(dp[1][j - 1][s], dp[0][j][s]); //next转移 for(int nxt = 0; nxt < KIND; nxt++) { now = goStatus(k, nxt); if(reachEnd(now)) add(ans2, dp[0][j][s]); else add(dp[1][j + 1][now - pool], dp[0][j][s]); } } } memcpy(dp[0], dp[1], sizeof(dp[0])); } return make_pair(ans1, ans2); } int main() { int n, day; while(scanf("%s", nowStr) == 1) { initialize(); scanf("%d%d", &day, &n); for(int i = 0; i < n; i++) { scanf("%s", str); insert(str); } build(); calDepth(root, 0); pair ans = DP(nowStr, day, n); printf("%d %d\n", ans.first, ans.second); } return 0; }
转载于:https://www.cnblogs.com/ronaflx/archive/2011/09/15/2178027.html
AC自动机好题