【洛谷P3435】OKRPeriods of Words【KMP】

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P3435
求一个字符串“前缀的前缀”的长度和。

思路：

“前缀的前缀”。。。难道不像 $n e x t$ 数组吗？
首先先求出一个正常的 $n e x t$ 数组，之后很容易发现， $n e x t [n e x t [i]]$ 也是 $i$ 的一个前缀，那么就很容易了。对于每一个 $i$ ，求出大于0的最小的 $j = n e x t [n e x t [n e x t [n e x t [. . . . . . i]]]]$ ,然后长度为 $i$ 的答案就是 $i - j$ 。
之后考虑优化。很容易发现， $n e x t$ 数组的递归次数太多了，需要减少。那么就每次求出 $j$ 时，优化 $n e x t [i] = j$ （因为其他都没用了，反正最后都要跳到 $j$ ），那么当以后的 $n e x t [n e x t [. . . k]] = i$ 时，就可以直接跳到 $j$ 了。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int len,j,next[1000101];
long long sum;
char s[1000101];

int main()
{
    scanf("%d",&len);
    cin>>s;
    j=0;
    for (int i=1;i<len;i++)  //求next数组
    {
        while (j&&s[i]!=s[j]) j=next[j];
        if (s[i]==s[j]) j++;
        next[i+1]=j;
    }
    for (int i=1;i<=len;i++)
    {
        j=i;
        while (j&&next[j]) j=next[j];
        if (next[i]) next[i]=j;  //优化，减少次数
        sum+=(long long)(i-j);
    }
    cout<<sum;
    return 0;
}