题目大意
给出一个长度为 $n$ 的字符串 $s$ 要求你求出 $s$ 的每一个前缀在 $s$ 中出现的次数之和。$n\le 200000$。
解题思路
暴力的对每一个前缀进行一次匹配，求出出现次数后求和。
那肯定是不行的，复杂的是 $O(n\times (m+n))$ 的，不用想也知道要 TLE 那我们考虑 $KMP$ 中 $next$ 数组的性质：为每一个前缀的前缀和后缀最长的共同子串的长度。
那这不就是说如果 $next[i] = j$ 的话，那么在 $s$ 中 $1\rightarrow j$ 和 $i-next[i]+1\rightarrow i$ 这两个子串是相等的。同时也代表 $1\rightarrow j$ 这个前缀的出现次数多了 $1$。
这就好办了。我们只需要求出 $s$ 的 $next$ 数组，然后就可以算出前缀的出现次数。但是要注意算出的 $next$ 并不能直接求出出现次数。因为 $next$ 数组存储的是位置。所以要一步一步推过来，很容易就能得到一个递推式 $f[i] = f[nxt[i]]+1$ 到最后统计一遍总和就可以得到答案了。
放上代码
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int maxn = 2e5+3, HA = 1e4+7; int T, p, Ans, nxt[maxn], dp[maxn], n; char s[maxn]; inline void Getnext() { for(int i=2; i<=n; i++) { p = nxt[i-1]; while(p && s[p+1] != s[i]) p = nxt[p]; if(s[p+1] == s[i]) nxt[i] = p+1; else nxt[i] = 0; } } int main() { scanf("%d", &T); while (T--) { memset(nxt, 0, sizeof(nxt)); memset(dp, 0, sizeof(dp)); Ans = 0; scanf("%d", &n); scanf("%s", s+1); Getnext(); dp[0] = 0; for(int i=1; i<=n; i++) { dp[i] = dp[nxt[i]] + 1; dp[i] = dp[i] % HA; } for(int i=1; i<=n; i++) Ans = (Ans % HA + dp[i] % HA) % HA; printf("%d\n", Ans); } }