大二训练第一周 A - The Minimum Length

来源:转载

大二训练第一周 A - The Minimum Length,有需要的朋友可以参考下。


A -The Minimum LengthTime Limit:1000MSMemory Limit:131072KB64bit IO Format:%lld & %lluSubmitStatus

Description

There is a string A. The length of A is less than 1,000,000. I rewrite it again and again. Then I got a new string: AAAAAA...... Now I cut it from two different position and get a new string B. Then, give you the string B, can you tell me the length of the shortest possible string A. For example, A="abcdefg". I got abcdefgabcdefgabcdefgabcdefg.... Then I cut the red part: efgabcdefgabcde as string B. From B, you should find out the shortest A.

Input

Multiply Test Cases. For each line there is a string B which contains only lowercase and uppercase charactors. The length of B is no more than 1,000,000.

Output

For each line, output an integer, as described above.

Sample Input

bcabcabefgabcdefgabcde

Sample Output

3

7

求一个串的最小循环长度 如果循环直接输出 n-suffix[n]就是答案了

ACcode:

#pragma warning(disable:4786)//使命名长度不受限制#pragma comment(linker, "/STACK:102400000,102400000")//手工开栈#include <map>#include <set>#include <queue>#include <cmath>#include <stack>#include <cctype>#include <cstdio>#include <cstring>#include <stdlib.h>#include <iostream>#include <algorithm>#define rd(x) scanf("%d",&x)#define rd2(x,y) scanf("%d%d",&x,&y)#define rds(x) scanf("%s",x)#define rdc(x) scanf("%c",&x)#define ll long long int#define maxn 1000100#define mod 1000000007#define INF 0x3f3f3f3f //int 最大值#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)#define MT(x,i) memset(x,i,sizeof(x))#define PI acos(-1.0)#define E exp(1)using namespace std;int suffix[maxn];char str[maxn];int main(){ while(rds(str)!=EOF){MT(suffix,0);int i,j;j=suffix[0]=-1;i=0;int m=strlen(str);while(i<m){while(-1!=j&&str[i]!=str[j])j=suffix[j];suffix[++i]=++j;}printf("%d/n",m-suffix[m]); } return 0;}/*bcabcabefgabcdefgabcde*/


版权声明:本文为博主原创文章,未经博主允许不得转载。



分享给朋友:
您可能感兴趣的文章:
随机阅读: