OKR-Periods of Words

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 862 字

KMP沿border链求各前缀最大周期

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1468
// 题意：给长度 k 的字符串，对每个前缀求其"最大周期"（Q 为 A 的真前缀且 A 是 QQ 的前缀）长度并求和。
// 思路：求前缀函数后，对每个前缀沿 nxt 链跳到最短的 border j，若有 border 则贡献 i-j，同时把 nxt[i] 压缩到 j 加速后续。
// 复杂度：O(k) 时间 / O(k) 空间
// 易错点：没有 border 的前缀贡献为 0 而不是 i；路径压缩必须在算完贡献之后再写，否则 nxt[i] 非零判断会失真。
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    if(!(cin>>k)) return 0;
    string s;
    if(!(cin>>s)) return 0;
    vector<int> nxt(k+1,0);
    for(int i=1;i<k;i++){
        int j=nxt[i];
        while(j>0&&s[i]!=s[j]) j=nxt[j];
        if(s[i]==s[j]) j++;
        nxt[i+1]=j;
    }
    long long ans=0;
    for(int i=1;i<=k;i++){
        int j=i;
        while(nxt[j]) j=nxt[j];
        if(nxt[i]){
            ans+=(long long)(i-j);
            nxt[i]=j;
        }
    }
    cout<<ans<<'\n';
    return 0;
}

OKR-Periods of Words

正文

一本通·提高篇的其它内容