首页 > 代码库 > HUST - 1010 The Minimum Length

HUST - 1010 The Minimum Length

2024-07-22 07:31:48   216人阅读

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 abcdefgabcdefgabcdefgabcdefg.... 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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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;
}


HUST - 1010 The Minimum Length


联系
我们