KMP相关题目

求成为两倍前缀的前缀长度之和，那么我们就用 \(F(nxt)\) 数组的性质：

前缀 \(i\) 的长度为 \(F[i]\) 的前缀和后缀是相等的

说明，如果有 \(i\) 一个公共后缀长度为 \(j\) ，那么这个前缀 \(i\) 就有一个周期为 \(i-j\).

那么我们就有以下解法：

先求出 \(F\) 数组，对于每个前缀 \(i\) ,令 \(j=i\), 然后在 \(j>0\) 的情况下，令 \(j=F[j]\), 最小的 \(j\) 就是答案，为 \((i-j)\) 。

答案就是加和。

这道题其实题意很简单：给定一个多边形，求对称轴的数量。

思考一下，暴力枚举肯定不可行，我们就把问题转化一下：

将多边形顺时针转一圈，将角和边的值连在一起就成了环

假如有一个边长为 \(1\) 的等边三角形，则它的角和边序列应该是： \(1,60°,1,60°,1,60°\)，围成一个含有 \(2n\) 个元素的环（角为环上的边，边为环上的结点）。

将 \(1,60°\) 记为 \(a,b\) ,则环为：

而对称轴会把这些点分成两部分，且两部分完全一样，对应到序列上就是：断开环上的某一条边，且连成的序列是回文的

对于环的处理：一种常见的处理方法是选择任意一个位置断开，将序列复制成为2倍长度的链。

然后就可以在这条长度为 \(4n\) 的链上找长度为 \(2n\) 的回文串。

怎么找回文串？用 \(KMP\) 是个好方法：

先选择任意一个位置断开，记该序列为 \(S_0\) ,再复制一遍得到序列 \(S\) ，将 \(S_0\)反过来得到串 \(T\) ，求 \(S\) 中有多少个位置和 \(T\) 匹配即可.

同时运用了计算几何相关知识。