[BOI2009] Radio Transmission 无线传输

题目描述

给你一个字符串 \(s_1\)，它是由某个字符串 \(s_2\) 不断自我连接形成的（保证至少重复 \(2\) 次）。但是字符串 \(s_2\) 是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行一个整数 \(L\)，表示给出字符串的长度。

第二行给出字符串 \(s_1\) 的一个子串，全由小写字母组成。

输出格式

仅一行，表示 \(s_2\) 的最短长度。

样例 #1

样例输入 #1

8 cabcabca

样例输出 #1

3

提示

样例输入输出 1 解释 对于样例，我们可以利用 \(\texttt{abc}\) 不断自我连接得到 \(\texttt{abcabcabcabc}\)，读入的 \(\texttt{cabcabca}\)，是它的子串。

规模与约定 对于全部的测试点，保证 \(1 < L \le 10^6\)。

按照题意，我们要求的是\(s_2\)的最短长度，也就是\(s_1\)最小的循环字串。 这里实际上有一个结论：答案就是\(n-pmt[n-1]\)。(可能有的结论是\(n-pmt[n]\)，只是因为下标是从1开始) 具体证明可以看这篇博客：（写得很清楚了） 大佬的详解 下面贴上代码：

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

补充证明

在这里插入图片描述 上面的前后缀是\(max(border)\)。不妨记上面的前缀为\(s_1\)，下面的后缀为\(s_2\)。 我们可以发现在这里插入图片描述 箭头联系起来的各部分是相等的，也就是\(s_1[1]=s_2[2]、s_1[2]=s_2[3]、s_1[3]=s_2[4]······\)，由此类推。 同时，又因为\(s_1[1]=s_2[1]、s_1[2]=s_2[2]、s_1[3]=s_2[3]······\)，将两者联系起来，我们可以得到： \[s_1[i]=s_2[j]|1<=i<=5，1<=j<=5\] 那有没有可能：更一般的情况是：\(s_1\)红色部分的后面加上一小段普通的字符串\(t\)。 我们可以分析一下：实际上这是可能的。我们可以结合样例进行分析。（这里不写了，样例的解释很清楚，可以认为：最后的循环节被强行切割了一部分。） 所以我们总结一下上面的内容：红色部分的字符串就是我们要求的最小循环节了。 所以问题转化为：求\(max(border)\)。 只需要求出\(pmt[n-1]\)即可，那么\(n-pmt[n-1]\)就是答案了。

AC代码：

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