UVA10298

Power Strings

题面翻译

题意简述：

求一个字符串由多少个重复的子串连接而成。

例如 ababab 由三个 ab 连接而成，abcd 由 abcd 由一个 abcd 连接而成。

输入格式

本题多组数据。

每一组数据仅有一行，这一行仅有一个字符串 \(s\)。

输入的结束标志为一个 .。

输出格式

对于每一组数据，输出这组字符串由多少个重复的子串连接而成。

说明/提示

\(1\le |s|\le 10^6\)。

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

abcd aaaa ababab .

样例输出 #1

1 4 3

其实方法还是一样的，求出最短的循环节(记作\(p\))，也就是\(n-pmt[n-1]\)，然后就是\(n/(n-pmt[n-1])\)。 但是，这里需要注意的是：\(s\)可能不是由整数个\(p\)构成的，可能存在最后的\(p\)被切割的情况。（一开始没考虑到这点，看了题解才反应过来）。 那么这里就需要进行特叛了：如果\(n\)%\((n-pmt[n-1])==0\)，说明恰好整除，那么\(n/(n-pmt[n-1])\)就是答案了。 如果\(n\)%\((n-pmt[n-1])!=0\)，那么只能以\(s\)自身作为循环节了，答案也就是1。 具体的证明可以看看评论区的大佬，写的很好：https://www.luogu.com.cn/blog/hzz/solution-uva10298

AC代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e6+10;
int pmt[MAXN];
void get_pmt(const string &s){
    for(int i=1,j=0;i<s.length();i++){
        while(j&&s[i]!=s[j])j=pmt[j-1];
        if(s[i]==s[j])j++;
        pmt[i]=j;
    }
}
int main(){
    while(1){
        string s;
        getline(cin,s);
        if(s.length()==1&&s[0]=='.')break;
        get_pmt(s);
        int n=s.length();
        if(n%(n-pmt[n-1])==0)cout<<n/(n-pmt[n-1])<<"\n";
        else{
            cout<<1<<"\n";
        }
    }
    return 0;
}

注意事项

因为这道题目是有多个数据输入，且一行一个\(s\)，所以我们可以用\(getlin(cin,s)\)，只需要当\(s\)为"\(.\)"时结束即可。

结论总结：

设字符串的长度为\(n\)，最长相同前后缀的长度为\(pmt[n-1]\)。如果\(n\)%\((n-pmt[n-1])==0\)，则答案为\(n/(n-pmt[n-1])\)，否则为1。