晚上不想写代码，就水一发博客吧qwq。
P2444 [POI2000]病毒
无限长的字符串就是能在\(ACAM\)上无限跑下去而不会撞到已有的字符串，所以建出\(ACAM\)判环即可。P3763 [TJOI2017]DNA
建出\(SAM\)之后，由于可以有错误匹配的机会，所以我们可以考虑\(dp\)。令\(dp[i][j]\)表示匹配到\(i\)这个节点时错误了\(j\)次匹配是否可行，当然，写个记忆化搜索就好了。P3966 [TJOI2013]单词
\(ACAM\)板题……不过我还是一眼看成\(SAM\)…… 把所有字符串拼在一起，两两之间新增一个其它字符，然后把这个大字符串插到\(SAM\)里，最后把每个串往上跑就好了。由于每个串都存在，所以连\(parent\)树都不用跳，好写的一批。P4051 [JSOI2007]字符加密
\(SA\)定义 不过我很好奇，\(SA\)是\(09\)年的论文，\(07\)年他们是怎么做的？P3649 [APIO2014]回文串
回文树板题，树形\(dp\)出每个点（串）的\(size\)然后和\(len\)乘一下就好了，和\(SAM\)板子几乎是一样的。P4094 [HEOI2016/TJOI2016]字符串
这个问题转化还是比较妙的 首先可以明确，\([a,b]\)中所有子串有意义的其实只有以\(b\)为右端点的那些后缀，所以一种暴力的做法就是枚举左端点再和\([c,d]\)算\(lcp\)。对此，我们可以二分答案，显然如果\(maxlcp=x\)的话，任意小于\(x\)的\(lcp\)都是可以取到的（一起删去末尾不就好了）。 接下来，我们就把原问题转化成了一个判定性问题：判断\([a,b-mid+1]\)为左端点，b为右端点的子串与\([c,d]\)的子串是否有\(lcp\)大于等于\(mid\)的。这样的话，我们可以在\(SA\)中找到与\([c,d]\)的\(lcp\)大于等于\(mid\)的所有串（暂且叫做\(sa_{l…r}\)），那么接下来的问题就是询问\(i∈[a,b-mid+1]\)且\(rnk_i∈[l,r]\)的\(i\)是否存在。把\(i\)看做下标，\(rnk_i\)看做权值，这就是主席树板子了。P5108 仰望半月的夜空
考虑贪心，对于长度为\(i\)的子串，我们必然要在\(SA\)上找到第一个长度大于等于\(i\)的子串，这个串的前\(i\)位必然是长度为\(i\)的子串中字典序最小的。在这个基础上，由于位置也要满足最小，那么就是与上述的这个串的\(lcp\)大于等于\(i\)的\(sa\)最小的。我们枚举\(i\)，由于\(i\)单调递增，那么上述那个串的位置也必然是单调不降的，复杂度就有保证了。P4036 [JSOI2008]火星人
带插入修改的\(lcp\)……考虑\(lcp\)除了可以\(SA\)，也可以用二分+哈希。对此，我们建一颗\(Splay\)出来，每个点维护子树内的\(Hash\)值，对于询问\(lcp\)，二分之后在\(Splay\)对应区间判断\(Hash\)是否相等就好了。P3193 [HNOI2008]GT考试
令\(dp[i][j]\)表示当前匹配到大串第\(i\)位、小串第\(j\)位的方案数，转移就是\(dp[i][j] -> dp[i + 1][nxt[j][c]]\)，\(c\)是枚举的字符，\(nxt\)表示小串第\(j\)位向\(c\)这个字符走一步会到什么位置，这个可以\(KMP\)预处理。由于状态相同，直接上矩乘就好了。P4052 [JSOI2007]文本生成器
把上一个题搞到了\(AC\)自动机上，然后不用矩乘了，经过补集转化之后就和上个题就一模一样了。P3311 [SDOI2014]数数
和上一题的区别是多了个不超过\(N\)的限制。设\(f[i][j]\)表示大串走到第\(i\)位，在\(AC\)自动机上的第\(j\)位且前\(i\)位和\(N\)相同（以下称为卡上界）的方案，\(g[i][j]\)表示不卡上界的方案，那么就有：\(f[i][j]->f[i+1][ch[j][N_{i+1}]]\)\(f[i][j]->g[i+1][ch[j][c]]\)\(g[i][j]->g[i+1][ch[j][c]]\)\(c\)表示小于\(N_{i+1}\)的数字。然后要注意一下前导零的问题，我一开始就拿着零往\(ACAM\)上跑，结果死活调不出来…… 这份代码饱含人类智慧……网上各种代码都又长又难懂……#include#include #include #include const int maxn = 1507;const int mod = 1e9 + 7;using namespace std;int n, m;char s[maxn], t[maxn];int ch[maxn][10];int fa[maxn];int ed[maxn];int cnt;int f[maxn][maxn];int g[maxn][maxn];inline void insert(char *s){ int x = 0; for (int i = 0; s[i]; i++) { int c = s[i] - '0'; if (!ch[x][c]) ch[x][c] = ++cnt; x = ch[x][c]; } ed[x] = 1;}inline void build(){ queue q; for (int i = 0; i <= 9; i++) if (ch[0][i]) q.push(ch[0][i]); while (!q.empty()) { int x = q.front(); ed[x] |= ed[fa[x]]; q.pop(); for (int i = 0; i <= 9; i++) if (ch[x][i]) fa[ch[x][i]] = ch[fa[x]][i], q.push(ch[x][i]); else ch[x][i] = ch[fa[x]][i]; }}int main(void){ scanf("%s", t + 1); int n = strlen(t + 1), m, ans = 0; cin >> m; while (m--) { scanf("%s", s); insert(s); } build(); int w = 0; for (int i = 1; i <= n; i++) { w = ch[w][t[i] - '0']; if(ed[w]) break; f[i][w] = 1; } for (int i = 0; i < n; i++) for (int j = 0; j <= cnt; j++) for (int k = 0; k <= 9; k++) { if (ed[ch[j][k]]) continue; if (!j && k && (i || k < t[i + 1] - '0')) ++g[i + 1][ch[j][k]] %= mod; //解决前导零的问题 if (k < t[i + 1] - '0') (g[i + 1][ch[j][k]] += f[i][j]) %= mod; (g[i + 1][ch[j][k]] += g[i][j]) %= mod; } for (int i = 0; i <= cnt; i++) ans = (ans + g[n][i]) % mod; cout << (ans + f[n][w]) % mod << endl; return 0;}
P4555 [国家集训队]最长双回文串
回文树板题，但我还是选择了更好写的\(Manacher\)，不过我还是有点疑惑为什么我最初的思路会错，而且错的很少，得了93分。后来照着题解改了两句话就过了，还是懵逼啊…… 不管做没做过优秀的拆分都能看出，我们只要求以每个点为左端点和右端点的最长的回文串，这个可以在跑\(Manacher\)的时候求出来。具体实现还是看其他人的题解吧，毕竟我自己都不知道自己为什么会错……P2414 [NOI2011]阿狸的打字机
总算把这大坑填了……这题在任务计划里呆了长达\(9\)个月之久…… 不过的确是道好题。首先按照题意模拟，小写字母就往下建节点，\(P\)就打\(ed\)标记，\(B\)就往回走，得到一个\(trie\)之后把它建成\(ACAM\)。 接下来，对于一次询问，暴力做的话是拿\(y\)串往\(ACAM\)上跑，然后把经过的每一个点的\(fail\)指针都跳一遍，统计有多少个点通过跳\(fail\)经过了\(x\)串的节点。这个问题可以转化成：询问匹配\(y\)串经过的点有多少个在\(fail\)树上\(x\)的子树内。同样的套路，把\(y\)串经过的点看作下标，其在\(fail\)树上的\(dfs\)序看作权值，直接树上主席树即可。P1659 [国家集训队]拉拉队排练
注意\(k\)要开\(long~long\)以及只统计奇数回文串。未完待续……