BZOJ 1355[Baltic2009]Radio Transmission（KMP）

题意

给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少.

(n<=1000000)

题解

这种求最小循环节的题一般是KMP。

因为有一个很强的结论if（len%(len-nxt[len])==0)那这个字符串的最小环节为len-nxt[len]。

又因为题目说明给出的是有循环节的，所以直接输出len-nxt[len]就行了。

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int N=;

 int n,nxt[N];

 char s[N];

 int main(){

     scanf("%d",&n);

     scanf("%s",s+);

     nxt[]=;

     for(int i=,j=;i<=n;i++){

         while(j&&s[j+]!=s[i])j=nxt[j];

         if(s[j+]==s[i])j++;

         nxt[i]=j;

     }

     printf("%d",n-nxt[n]);

     return ;

 }

巴特西

BZOJ 1355[Baltic2009]Radio Transmission（KMP）

题意

题解

最新文章

热门文章