题解 P3435 【[POI2006]OKR-Periods of Words】

· · 题解

2019. 10. 26: 换了一张图

这是一道让我们深入了解KMP算法精髓的好题。

题目中的“匹配前缀”我们可以这样理解：在A的前缀中，把这个前缀再叠加一遍后就把A包括进来，如图：

那么，"abcabcab"的最长匹配子串应该是"abcabc"，长度为6。

我们设第一个图中字符串为S，第二个字符串为SS，显然有S[6..8]=SS[6..8]=SS[1..2]=S[1..2]。于是我们得到规律，匹配前缀子串满足KMP算法中“前缀等于后缀”的性质，我们要使子串最长，那么这个匹配长度应该尽可能小。比如对于S来说,next[8]应该为5，表示S[1..5]和S[4..8]是匹配的，但我们选择的是最短的匹配长度short[8]=2,S[1..2]=S[7..8]，而答案就是8-short[8]=6。

但是KMP只能求出每个前缀串的最长匹配长度，如果要求出最短匹配长度，我们可以一直递推next[i],next[next[i]]...，直到为0. 熟悉的KMP本质的人都应该知道为什么，这里举一个例子。

在S中，next[8]=5,而next[5]=2，next[2]=0了，所以next[5]=2就是8的最短匹配长度，将8-2累计到答案中即可。

最后，类似求next时的递推方法，我们可以递推short来提高效率。比如在上例中,我们得到short[8]=2后，就直接将next[8]修改为2，这样8以后的数字如果递推到8了就可以直接跳到next[2]=0，而不用跳到next[5]这里。

答案记得long long，否则只有40分。

#include <bits/stdc++.h>
#define MAX (1000000+50)
using namespace std;

int size,nxt[MAX];
char s[MAX];
unsigned long long ans;//记得开long long

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cin>>size>>(s+1);
    for (register int i=2,j=0; i<=size; i++)
    {
        while (j && s[i]!=s[j+1]) j=nxt[j];
        if (s[i]==s[j+1]) j++; nxt[i]=j;
    }//KMP求解next数组
    for (register int i=2,j=2; i<=size; i++,j=i)
    {
        while (nxt[j]) j=nxt[j]; //递推求最短匹配长度
        if (nxt[i]) nxt[i]=j; //修改next[i]的值
        ans+=i-j;//统计答案
    }
    cout<<ans<<endl;
    return 0;
}