hust--------The Minimum Length (最短循环节)(kmp)
hust--------The Minimum Length (最短循环节)(kmp)
F - The Minimum Length
Time Limit:1000MS Memory Limit:131072KB 64bit IO Format:%lld & %llu
Submit Status
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 abcd efgabcdefgabcdefgabcdefg.... 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
bcabcab
efgabcdefgabcdeSample Output
3
7
代码： 1 #include<iostream>
2 #include<cstring>
3 #include<cstdlib>
4 #include<cstdio>
5 using namespace std;
6 const int maxn=1000050;
7 int next[maxn];
8 char str[maxn];
9 int main()
10 {
11 int i,j;
12 while(scanf("%s",str)!=EOF)
13 {
14 j=-1;
15 i=0;
16 next[i]=-1;
17 int len=strlen(str);
18 while(i<len)
19 {
20 if(j==-1||str[i]==str[j])
21 {
22 i++;
23 j++;
24 if(str[i]==str[j])
25 next[i]=next[j];
26 else next[i]=j;
27 }
28 else j=next[j];
29 }
30 //得到最大回缩长度（即最小循环长度;
31 int cir_len=len-next[len];
32 printf("%d\n",cir_len);
33 }
34 return 0;
35 }