「2.2」Radio Transmission
「2.2」Radio Transmission
题目描述
给你一个字符串,它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的,现在只想知道它的最短长度是多少。
输入格式
第一行给出字符串的长度 L,第二行给出一个字符串,全由小写字母组成。
输出格式
输出最短的长度。
样例输入1
8
cabcabca
样例输出1
3
注释说明
样例说明
对于样例,我们可以利用 abc 不断自我连接得到 abcabcabc,读入的 cabcabca 是它的子串。
数据范围与提示
对于全部数据,1≤L≤10^6。
//i%(i-next[i])==0&&next[i]!=0 ,
//则字符串前i位循环,
//而且循环节长度:i-next[i],
//循环次数: i/( i-next[i])
#include <bits/stdc++.h>
using namespace std;
int n,ne[1000003],np,ns;
string s,p;
int main() {
cin>>np;
cin>>p;
p=" "+p;
for(int i=1,j=0; i<np; i++){
while(j&&p[i+1]!=p[j+1])j=ne[j];
if(p[j+1]==p[i+1])j++;
ne[i+1]=j;
//cout<<j;
}
cout<<np-ne[np]<<"\n";
}
/*
cabcabcaa
*/