|
Description 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
题意：有一个字串A，现在利用A组成了一个新的字符串AAAAA...,现在从这个新的字符串的两个不同位置剪下去得到字符串B，问A的最小长度
思路：求A的最小长度，环句话就是说求B的最的最小循环节
#include
#include
#include
#include
using namespace std; const int maxn = 1000005; char pattern[maxn]; int next[maxn]; int main() { while (scanf("%s", pattern) != EOF) { int m = strlen(pattern); next[0] = next[1] = 0; for (int i = 1; i < m; i++) { int j = next[i]; while (j && pattern[i] != pattern[j]) j = next[j]; next[i+1] = pattern[i] == pattern[j] ? j+1 : 0; } printf("%d\n", m-next[m]); } return 0; }
|