POJ1961
6888 단어 poj
Time Limit: 3000MS
Memory Limit: 30000K
Total Submissions: 9792
Accepted: 4477
Description
For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as A
K ,that is A concatenated K times, for some string A. Of course, we also want to know the period K.
Input
The input consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S.The second line contains the string S. The input file ends with a line, having the
number zero on it.
Output
For each test case, output "Test case #"and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.
Sample Input
3
aaa
12
aabaabaabaab
0
Sample Output
Test case #1
2 2
3 3
Test case #2
2 2
6 2
9 3
12 4
Source
Southeastern Europe 2004
1 #include <cstdio>
2 #include <cstring>
3
4 using namespace std;
5
6 char s[1000010];
7 int next[1000010];
8
9 int main(void)
10 {
11 int i,j,n,len,th=1;
12
13 while(scanf("%d",&len)!=EOF && len)
14 {
15 scanf("%s",s);
16 printf("Test case #%d
",th++);
17 // KMP
18 i=-1;
19 j=0;
20 next[0]=-1;
21 while(j<len)
22 {
23 if(i==-1||s[i]==s[j])
24 {
25 i++;
26 j++;
27 next[j]=i;
28 }
29 else
30 i=next[i];
31 }
32
33 //
34 for(n=2;n<=len;n++)
35 if(n%(i=n-next[n])==0)
36 if((j=n/i)>1)
37 printf("%d %d
",n,j);
38 printf("
");
39 }
40
41 return 0;
42 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.