Radio Transmission

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

KMP求n减next[n]得最短循环长度

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1467
// 题意：给长度 L 和由某串自我连接而成的字符串，求生成它的最短串长度。
// 思路：求前缀函数 nxt，最长公共前后缀为 nxt[L]，答案即最小循环节长度 L-nxt[L]。
// 复杂度：O(L) 时间 / O(L) 空间
// 易错点：直接输出 L-nxt[L] 即可，不需要整除判断，因为原串是循环串的子串而非整周期串。
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int L;
    if(!(cin>>L)) return 0;
    string s;
    if(!(cin>>s)) return 0;
    vector<int> nxt(L+1,0);
    for(int i=1;i<L;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;
    }
    cout<<L-nxt[L]<<'\n';
    return 0;
}

Radio Transmission

正文

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