洛谷3435 [POI2006]OKR-Periods of Words

Luogu

BZOJ

分析

$\mathrm{KMP}$+阅读理解


首先翻译一下题目:

  • 如果存在串 $B$ ( $B$ 可以为空) ,使得 $A=PB$ ,那么称 $P$ 是 $A$ 的前缀。
  • 如果 $A\neq P$ 并且 $P$ 是 $A$ 的前缀,那么称 $P$ 是 $A$ 的 $\mathrm{proper}$ 前缀。
  • 如果 $Q$ 是 $A$ 的 $\mathrm{proper}$ 前缀,并且 $A$ 是 $QQ$ 的前缀,那么称 $Q$ 是 $A$ 的周期。
  • 如果 $Q$ 是 $A$ 的所有周期中长度最大的那个,那么称 $Q$ 是 $A$ 的最大周期。特殊的,如果 $A$ 不存在周期,那么 $A$ 的最大周期为空串。
  • 给出串 $S$ ,求 $S$ 的所有前缀的最大周期长度之和。

显然,如果前缀 $i$ 存在一个长为 $j$ 的公共前后缀,那么它就会有一个长为 $i-j$ 的周期。

$j$ 可以通过暴跳 $nxt$ 得到,然后要周期最长的话,也就是要求出最小的 $j$ 。

于是直接暴跳到 $nxt[j]=0$ 的 $j$ 处就行了。

这样子的话可以卡成 $O(n^2)$ ,考虑优化。

把每个前缀 $i$ 的答案存下来,这样子跳的时候就可以直接用,然后就是 $O(n)$ 的了。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

const int N=1000000+10;

int n;
char s[N];
int nxt[N],sh[N];

int main() {
    scanf("%d%s",&n,s+1);
    for (re int i=2,j=0;i<=n;++i) {
        while (j&&s[j+1]!=s[i]) j=nxt[j];
        if (s[j+1]==s[i]) ++j;
        nxt[i]=j;
    }
    ll ans=0;
    for (re int i=1;i<=n;++i) {
        if (nxt[i]) sh[i]=sh[nxt[i]];
        else sh[i]=i;
        ans+=i-sh[i];
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 26 日 12 : 57 PM

发表评论