HUST 1010 The Minimum Length

题目链接:点我

题目

---

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
efgabcdefgabcde

Sample Output

3
7

---

题意:

给你一段从一串循环字符串中截下来的字符串问原字符串的最小循环长度是多少,

思路:

KMP算法,我们先找出题目给的串中有最大的重复长度,然后就可以得答案了,

代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn = 1e6+10;
char s[maxn];
int nextt[maxn];

void getnextt(int len){
    memset(nextt, 0, sizeof(nextt));
    nextt[0] = -1;
    int i = 0;
    int  j = -1;
    while(i < len){
        if(j == -1 || s[i] == s[j]){
            ++i;
            ++j;
            nextt[i] = j;
        }else  j = nextt[j];
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    while(cin>>s){
        int len = strlen(s);
        getnextt(len);
        printf("%d\n",len - nextt[len]);
    }return 0;
}