BZOJ——T 1355: [Baltic2009]Radio Transmission

http://www.lydsy.com/JudgeOnline/problem.php?id=1355

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 964 Solved: 664
[Submit][Status][Discuss]

Description

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

Input

第一行给出字符串的长度,1 < L ≤ 1,000,000. 第二行给出一个字符串，全由小写字母组成.

Output

输出最短的长度

Sample Input

8
cabcabca

Sample Output

HINT

对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串

Source

求出A串在KMP算法中A的next数组设A的长度为N 则答案为A的前N-next[N]位

为什么？分两种情况讨论： next[N] > N/2 next[N] <= N/2

画个图比划比划~~

 1 #include <algorithm>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 const int N(1000000+5);
 7 int n,next[N];
 8 char s[N];
 9 
10 inline void Get_next()
11 {
12     int j=0;
13     for(int i=2;i<=n;i++)
14     {
15         for(;j>0&&s[i]!=s[j+1];) j=next[j];
16         if(s[i]==s[j+1]) j++;
17         next[i]=j;
18     }
19 }
20 
21 int main()
22 {
23     scanf("%d%s",&n,s+1);
24     Get_next();
25     printf("%d",n-next[n]);
26     return 0;
27 }

枚举循环节长度L 用哈希判断A[1…L],A[L+1…2L],A[2L+1…3L]……是否相等最后一个循环节长度可能不足L，特殊判断

但我T了、、、

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 
 6 using namespace std;
 7 
 8 #define ull unsigned long long
 9 #define p 233
10 const int N(1000000+5);
11 ull n,hash[N];
12 char s[N];
13 
14 inline void Get_hash()
15 {
16     for(int i=1;i<=strlen(s+1);i++)
17         hash[i]=hash[i-1]*p+s[i]-'a';
18 }
19 inline ull Check(ull x,ull y,ull P)
20 {
21     return hash[y]-hash[x-1]*P;
22 }
23 
24 int main()
25 {
26     scanf("%d%s",&n,s+1);
27     Get_hash();
28     ull P=p;
29     for(int L=1;L<=n;L++,P*=p)
30     {
31         bool flag=1;
32         for(int i=L+1;i<=n/L*L;i+=L)
33             if(Check(i,i+L-1,P)!=hash[L])
34             {
35                 flag=0;
36                 break;
37             }
38         if(!flag) continue;
39         for(int i=n/L*L+1;i<=n;i++)
40             if(s[i]!=s[i-n/L*L])
41             {
42                 flag=0;
43                 break;
44             }
45         if(!flag) continue;
46         printf("%d",L);
47         break;
48     }
49     return 0;
50 }

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。