约定
\(S/s\) ：字符串。
\(S[l,r]\)：区间 \([l,r]\) 形成的子串。
\(S^R\)：将字符串 \(S\) 翻转。
manacher
理论
字符串算法的精髓是最大的利用之前求出的信息，这就让增量法和自动机成了字符串算法中的核心思想。
manacher 算法可以在线性时间复杂度内求出以每个点为中心的极大回文子串长度。
算法实现中我们维护：
- mid：当前最大的回文子串的中心。
- r：当前最大的回文子串的右端点。
- \(len_i\)：以 \(i\) 为中心的回文半径。
考虑到回文串的长度有奇有偶，我们选择在每两个字符间插入一个无关字符，这样奇偶回文串的长度就都变成了 \(len_i - 1\)。
如果 \(i \lt r\)，即 \(i\) 在当前的最大回文串的影响范围内，因为当前串是关于 \(mid\) 对称的，所以可以用 \(i\) 关于 \(mid\) 的对称点的回文半径更新 \(i\)，并且要注意不能超出边界即 \(len_i = min(len_{mid * 2-i},r-i+1)\)，剩下的暴力匹配即可。
因为每次 \(r\) 至少右移 \(1\)，所以复杂度是线性的。
for(int i = 1; i <= n; i++){
if(i <= r) len[i] = min(r - i + 1, len[(mid << 1) - i]);
while(s[i-len[i]] == s[i+len[i]]) len[i]++;
if(i + len[i] > r){
mid = i;
r = i + len[i] - 1;
}
}
例题
最终的答案形如 \(S + pres_i^R\)，满足 \(pres_i\) 为回文串，要尽量缩小 \(pres_i\) 的长度，也就是找到最靠前的回文子串满足其右端点是原串的右端点。
P3501 [POI2010] ANT-Antisymmetry
类似于正常的 manacher 过程，只不过两个字符匹配的条件变成了 xor 等于 \(1\)。
KMP
理论
定义 \(nxt_i\) 表示 \(S[1,i]\) 的最长公共前后缀，首先考虑如何快速的求出一个字符串的 \(nxt\) 数组。
考虑 DP，\(nxt_i\) 仅可以从 \(S[1,i-1]\) 的公共前后缀转移过来，找到最大的可以接上 \(S_i\) 的 \(nxt\) 这个过程可以一直跳 \(nxt\) 实现，原理如下图：
因为 \(j\) 每次最多增加 \(1\)，复杂度最大的时候就是从 \(n\) 跳回 \(0\)，这样是线性的。
匹配的过程和求 \(nxt\) 类似，如果当前位置失配就跳 \(nxt\)，这样充分利用了一个串的信息，保证文本串的指针不会后移，所以复杂度也是线性的。
多项式在字符串匹配中的应用
考虑两个数相等的条件是什么 -> \(a-b = 0\)，那把这个东西放到字符串上就有了代数意义上的两个字符相等的判断依据：字符的匹配函数 \(cmp(x,y) = A_x - B_y\)，\(cmp(x,y) =0\) 说明 \(A_x = B_y\)。
有了这个东西后再定义一个字符串完全匹配函数：\(P(n) = \sum_{i=0}^{m-1}cmp^2(i, n-m+1+i)\)，\(P(n) = 0\) 说明以 \(n\) 为结尾，字符串 A 在字符串 B 中出现。至于为什么加平方？如果不加的话会出现正负相消的情况，只要两个字符串的字符集一样两个串就匹配了，不合法呢。
为了凑出好看的形式，我们将 \(A\) 翻转并用 \(i\) 代替 \(m - i - 1\)，有：
\[\begin{split} P(n) &= \sum_{i=0}^{m-1} (A_i- B_{n-i})^2\\ &= \sum_{i=0}^{m-1}A_i^2 + \sum_{i=0}^{m-1}B_{n-i}^2 - 2\sum_{i=0}^{m-1}A_iB_{n-i} \end{split} \]这就出来卷积式了，虽然上界比较迷，但是问题不大，直接大力出奇迹设成 \(max(n,m)\)。
这个东东还可以用来做通配符匹配：P4173 残缺的字符串
考虑通配符怎么搞？相当于强制把匹配函数的值设成零，一种方法是 \(cmp(x,y) = A_xB_y(A_x-B_y),'*' = 0\) ，这样通配符对应的匹配函数值一定是 \(0\)。推式子也和上面一样大力展开即可，这里就不写了。懒
例题
设 \(dp_{i,j}\) 表示 \([i,j]\) 的最短 \(Factoring\) 的长度，转移：\(dp_{i,j} = min(dp_{i,k},dp_{k+1,j})\)，考虑一个串的压缩相当于是找出最小的周期且这个串能恰好被表示成这个周期的若干倍，以周期来代替这个串，根据一些 \(border\) 的理论，一个串的最小周期是 \(n - nxt_{n}\)，直接做即可。
标签：nxt,匹配,sum,len,字符串,回文 From： https://www.cnblogs.com/Lkkaknoi/p/17775849.html