백준 4354 문자열 제곱

KMP알고리즘을 수행하면 계산되는 pi배열 ( 다른말로 실패함수)를 이용한다.

다음과 같은 표를 살펴보자

(len은 문자열의 길이를 의미)

문자열	pi[len]
abab	2
ababab	4
abcabc	3
aaaa	3
asd	0

pi[len]은 문자열의 접두사 = 접미사인 index +1을 가리킨다.

즉, pi[len]은 반복되는 문자열의 길이가 반복될 수 있는 최대 길이를 의미한다.

이 말은 다른 말로, len - pi[len]이 문자열에서 반복되는 부분문자열의 최소 길이이다.

그런데 만약 len-pi[len]이 len으로 나누어 떨어진다면? len은 위에서 말한 부분문자열로만 이루어져있는 것이다.

따라서 위의 예시처럼 text[0~len-pi[len]]만큼의 부분문자열이 반복되는 것을 볼수 있다.

한편, len-pi[len]이 len으로 나누어떨어지지 않는다면?

혹은 len-pi[len]이 len의 절반보다 크다면?

다음 예를 보자.

 

문자열	pi[len]
abcab	2
abkkab	2
abcabcabc	6

abcab의 경우는 나누어떨어지지 않는 경우이다. 이처럼 문자열 중간에 찌꺼기가 들어있으면 나누어 떨어지지 않는다.

abkkab의 경우는 len-pi[len]이 len의 절반보다 큰 경우이다. 부분 문자열이 문자열의 모든 부분을 차지하고 있지 않을 경우 이렇게 나타난다.

abcabcabc의 경우는 올바른 경우다. 

코드는 다음과 같다.

//deque.tistory.com
#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <string> 
#include <cstring>
using namespace std;
int pi[1000002];
int main() {
	while (true) {
		string str;
		getline(cin, str);
		if (str == ".") break;
		memset(pi, 0, sizeof(pi));
		int strLength = str.size();
		int j = 0;
		for (int i = 1; i < strLength; i++) {
			while (j > 0 && str[i] != str[j]) j = pi[j - 1];
			if (str[i] == str[j]) pi[i] = ++j;
		}
		int patternLen = pi[strLength - 1];
		if (strLength / 2 > patternLen && strLength % (strLength - patternLen) != 0) printf("%d\n", 1);
		else printf("%d\n", strLength / (strLength - patternLen));
	}
	return 0;
}