Power Strings

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

KMP前缀函数求最小循环节重复次数

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1457
// 题意：每行一个字母串，遇到单独一个半角句号 "." 结束，输出该串最多由多少个相同子串重复连接而成。
// 思路：求前缀函数 nxt，最小循环节长度为 n-nxt[n]，若 n 能被它整除则答案为 n/(n-nxt[n])，否则只能是 1。
// 复杂度：O(单串长度) 时间 / O(单串长度) 空间
// 易错点：只有整行恰好是 "." 才终止，含 "." 的普通串不算；n-nxt[n] 整除判断不能漏，否则 abababa 会算错。
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    while(cin>>s){
        if(s==".") break;
        int n=(int)s.size();
        vector<int> nxt(n+1,0);
        for(int i=1;i<n;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;
        }
        int p=n-nxt[n];
        if(n%p==0) cout<<n/p<<'\n';
        else cout<<1<<'\n';
    }
    return 0;
}

Power Strings

正文

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