【KMP】Period
6246 단어 KMP
Next[] 함수 깊이 이해, Next[] 현재 문자 앞 일치 문자 수, 직렬 길이 n-Next[i] = 직렬 내 순환 서브 직렬의 길이 p.
이 문제는 서브 순환 직렬 내 순환 절수를 구한다.
Problem 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 file 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
삼
aaa
십이
aabaabaabaab
0
Sample Output
Test case #1
2 2
3 3
Test case #2
2 2
6 2
9 3
12 4
1 #include<iostream>
2 #include<stdio.h>
3 using namespace std;
4
5 char s[1000001];
6 int Next[1000001];
7
8 void getNext(int n){
9 int i=0,j=-1;
10 Next[0]=-1;
11 while(i<n){
12 if(j==-1||s[i]==s[j]){
13 i++;j++;
14 Next[i]=j;
15 }
16 else j=Next[j];
17 }
18 }
19
20 int main()
21 {
22 int n,k,t=1,p;
23 //freopen("pe.txt","r",stdin);
24 while(cin>>n&&n>1&&n<1000001){
25 cin>>s;
26 getNext(n);
27 cout<<"Test case #"<<t++<<endl;
28 for(k=2;k<=n;k++){
29 p=k-Next[k]; //
30 if(k%p==0&&k/p>1)
31 cout<<k<<' '<<k/p<<endl; // , k
32 }
33 cout<<endl;
34 }
35 return 0;
36 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
알고리즘 - Knuth, Morris, Prett흔히 찾는 문자나 문자열이 있는 지 없는 지를 확인할 때는 주로 if pattern in words 이런 식으로 검사를 할 수 있다. pi 테이블은 찾으려는 문자열(pattern)의 정보를 저장하고 있는 배열, 자료...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.