P2375 非常棒的 KMP 水题，感觉自己的思路比题解区靠前的绝大部分题解都简单，在洛谷远古题新题解的曝光量不高，所以在这写这篇题解。
题意
多组数据，给定字符串 S，求对于 S 的每一个前缀 S_{1\cdots i}，它的长度 \le \frac{i}{2} 的 border 前缀数量 \text{num}_i 你需要输出 \prod(\text{num}_i+1)，对 10^9+7 取模。
T\le5,\vert S\vert\le10^6
思路
这是我的 KMP 预处理板子，后面的代码看不懂的时候可以和这个对比一下：
for(int i = 1,j = 0;i < m;i ++){//每一轮给 S_{1...i+1} 找最长的 border
while(j && s[i + 1] != s[j + 1]) j = nxt[j];//下一个匹配不上，回跳
if(s[i + 1] == s[j + 1]) j ++;//匹配上了 +1
nxt[i + 1] = j;
}
我们用 \text{nxt}_i 表示 S_{1\cdots i} 的最长 border。
考虑刨去长度限制，能不能求 S 的每个前缀的 border 数量 \text{cnt}_i （不包括这个前缀本身）？
思考两分钟后还想不到再打开，这一步非常简单
如果 nxt_i 为零，cnt_i=0；否则，S_{1\cdots \text{nxt}_i} 是 S_{1\cdots i} 的一个 border，前者的 border 就是后者的其他 border，所以 \text{cnt}_i=\text{cnt}_{\text{nxt}_i}+1
于是我们线性求出了 \text{nxt} 数组和 \text{cnt} 数组。代码：
for(int i = 1,j = 0;i < m;i ++){
while(j && s[i + 1] != s[j + 1]) j = nxt[j];
if(s[i + 1] == s[j + 1]) j ++;
nxt[i + 1] = j;
cnt[i + 1] = j ? cnt[j] + 1 : 0;//比板子就多了这一行
}
然后令我们要求的数组为 \text{num}。
根据求 \text{cnt} 的思想，我们只需要找到 S_{1\cdots i} 的最长的长度 \le\frac{i}{2} 的前缀 S_{1\cdots j}，\text{num}_i 就是 \text{cnt}_j+1 （这个 border 和这个 border 的所有 border）。
怎么找 S 所有前缀的最长的不长于此前缀一半的 border 呢？
也非常简单，思考两分钟
观察 KMP 的过程，S_{1\cdots i} 的最长 border 一定来自于一个 S_{1\cdots i-1} 的 border（“来自于”即在后者的后面加上 S_i 获得）。
再跑一遍 KMP，加上限制 2(j+1)\le i，不满足就得往回跳 j=nxt[j] 即可。
感性理解：很显然是正确的，不让 border 的长度到一半就可以了。
正确性：S_{1\cdots i} 的满足条件的最长 border S_{1\cdots j}，有 2j\le i，是由 S_{i\cdots i-1} 的 border S_{1\cdots j-1} 推导过来的，显然 2j\le i\rightarrow 2(j-1)\le i-1，所以这个 S_{1\cdots j-1} 是一个 S_{1\cdots i-1} 的合法的 border，不合法 border（$2(j-1)>i-1$）是一定不会影响后面推导的。
因此，强行添加限制排除所有的不合法 border 并不会影响正确性。
高效性：时间复杂度同 KMP，证明同 KMP。
此部分代码：
for(int i = 1,j = 0;i < m;i ++){//式子不一样是因为我的 KMP 实质上是在匹配 i+1 和 j+1，
while(j && (s[i + 1] != s[j + 1] || 2 * j >= i)) j = nxt[j]; //2j<=i 就变成了 2(j+1)<=i+1，
if(s[i + 1] == s[j + 1] && 2 * j < i) j ++;//化简后就是 2j<i。
num[i] = j ? cnt[j] + 1 : 0;
}
代码
多组数据{
read_string s[1...n]
for(int i = 1,j = 0;i < n;i ++){//KMP 板子，额外统计 border 数量
while(j && s[i + 1] != s[j + 1]) j = nxt[j];
if(s[i + 1] == s[j + 1]) j ++;
nxt[i + 1] = j,cnt[i + 1] = cnt[j] + (j > 0);
}
for(int i = 1,j = 0;i < n;i ++){
while(j && (s[i + 1] != s[j + 1] || 2 * j >= i)) j = nxt[j];//加上限制后回跳
if(s[i + 1] == s[j + 1] && 2 * j < i) j ++;//可以匹配
ans = ans * (cnt[j] + (j > 0) + 1) % MOD;//题目所求为 (num[i]+1) 的积
}
printf("%lld\n",ans);
}
