kmp 문자열 최소 주기

총 시간 제한: 
3000ms 
메모리 제한: 
65536kB
묘사 하 다.
두 문자열 a 와 b 를 지정 합 니 다. 우 리 는 a * b 를 그들의 연결 로 정의 합 니 다.하면, 만약, 만약... 그리고 b = "def", a * b = "abcdef" 입 니 다. 만약 우리 가 연결 을 곱셈 으로 고려한다 면, 마이너스 정수 가 아 닌 곱셈 은 일반적인 방식 으로 정의 할 것 이다. a ^ 0 = "(빈 문자열), a ^ (n + 1) = a * (a ^ n).
입력
모든 테스트 샘플 은 인쇄 가능 한 문 자 를 입력 하고 s 로 표시 합 니 다.s 의 길 이 는 적어도 1 이 고 백만 원 을 넘 지 않 습 니 다.마지막 테스트 샘플 뒤 에는 점 번호 가 한 줄 로 될 것 이다.
출력
모든 s 에 대해 서 는 최대 n 을 인쇄 하여 a 가 존재 하도록 해 야 합 니 다. s = a ^ n
샘플 입력

abcd
aaaa
ababab
.

샘플 출력

1
4
3

제시 하 다.
이 문 제 는 입력 량 이 많 습 니 다. cin 대신 scanf 를 사용 하여 시간 을 초과 하지 않도록 하 십시오.
근원
Waterloo local 2002.07.01
//poj 2406 power string 

#include 
#include 
#include 
using namespace std;

#define maxlen 1000000

char str[maxlen+1];
int next[maxlen+1];

void getNext(int len)
{
    int i = 0, j = -1;
    next[i] = j;
    while(i < len){
        if(j == -1 || str[i] == str[j]){
            i++, j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

int main()
{
    int len = 0;
    while(scanf("%s", str)){
        if(str[0] == '.') break;

        int len = strlen(str);
        getNext(len);
        if(len%(len-next[len]) || next[len] == 0)   //  len  (len-next[len])，      len-next[len]
            cout << 1 << endl;
        else
            cout << len/(len-next[len]) << endl;

    }
    return 0;
}

접두사 의 주기
총 시간 제한: 
3000ms 
메모리 제한: 
65536kB
묘사 하 다.
하나의 문자열 의 접 두 사 는 첫 번 째 문자 부터 연속 적 으로 몇 개의 문자 입 니 다. 예 를 들 어 "
abaab "는 모두 5 개의 접두사 가 있 는데 각각 a, ab, aba, abaa 이다. 
abaab。
N 비트 문자열 S 의 접두사 가 순환 절 이 있 는 지 알 고 싶 습 니 다.다시 말 하면 모든 처음부터 시작 하 는 길이 가 i (i 가 1 이상) 인 접두사 에 대해 중복 되 는 하위 문자열 A 로 구성 되 는 지, 즉 AAA... A (A 가 K 번 반복 되 고 K 가 1 이상).존재 한다 면 가장 짧 은 순환 절 에 대응 하 는 K 값 을 찾 아 보 세 요.
입력
여러 그룹의 테스트 데 이 터 를 입력 하 십시오.각 그룹의 테스트 데 이 터 는 두 줄 을 포함한다.
첫 번 째 줄 은 문자열 S 의 길이 N (2 < = N < = 1000 000) 을 포함 합 니 다.
두 번 째 줄 은 문자열 S 를 포함 합 니 다.
0 만 포함 하 는 줄 로 데 이 터 를 입력 하 십시오.
출력
각 그룹의 테스트 데이터 에 대해 첫 번 째 줄 은 'Test case \ #' 와 테스트 데이터 의 번 호 를 출력 합 니 다.
다음 줄 마다 접두사 길이 i 와 중복 측정 K 를 출력 하고 중간 에 빈 칸 으로 구분 합 니 다. 접두사 길 이 는 오름차 순 으로 배열 해 야 합 니 다.
각 그룹의 테스트 데이터 의 마지막 에 빈 줄 을 출력 합 니 다.
샘플 입력

3
aaa
12
aabaabaabaab
0

샘플 출력

Test case #1
2 2
3 3

Test case #2
2 2
6 2
9 3
12 4

#include 

using namespace std;

#define maxlen 1000000

char str[maxlen+1];
int next[maxlen];

void getNext(int n)
{
    int i = 0, j = -1;
    next[i] = j;
    while(i < n){
        if(j == -1 || str[i] == str[j]){
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

int main()
{
    int n, cases = 1;
    while(cin >> n){
    if(!n) break;

    cin >> str;
    getNext(n);

    cout << "Test case #" << cases++ << endl;
    for(int i = 1; i < n; i++){
        if((i+1)%(i+1-next[i+1]) == 0 && next[i+1])
            cout << i+1 << " "  << (i+1)/(i+1-next[i+1]) << endl;
    }
    cout << endl;
  }
}