백준4354 문자열 제곱 - C++ / KMP

KMP 알고리즘의 응용 문제.

 

문제를 잘 읽고 다시 생각해보면

전체가 될 수 있는 부분 문자열 중 최소 길이를 구하라는 뜻과 같다. 

즉 s = abcabcabcabc 문자열이 있다면

답의 후보는 abc, abcabc 가 되고, 그 중 더 짧은 abc 를 구하라는 얘기이다.

 

KMP 알고리즘은 찾고 싶은 문자열의 접두사/접미사 중 최대 길이의 Index를 미리 구해놓는데, 그 연장선이다.

 

인덱스를 부여하는 것과 이 문제를 연관시켜보자.

1. 부분 문자열은 항상 index 0 부터 시작해야 한다.

             -> abcabcabcabc 라면 부분 문자열은 bca 형태로 만들어질 수 없고 항상 a 부터 시작해야 한다.

2. 부분 문자열의 중간을 건너뛸 수 없다. 

             -> abcabcabcabc 에서 ab(c)abc 형태로 만들 수 없다

             -> s[i] != s[j] (i : s의 index, j : 접두사의 index)) 인 상황이라면 항상 i 전까지가 부분 문자열이 될 수 있다.

3. [전체 문자열 길이]/[부분 문자열 길이]는 항상 나누어 떨어져야 된다. 

 

위 3가지를 보면 쉽게 알 수 있다.

한 번이라도 j(겹치는 부분 문자열의 마지막 index)가 0이 나오면 그것은 나눠 떨어지는 부분 문자열을 가질 수 없다.(2)

항상 처음부터 시작해야하기 때문에 부분 문자열의 길이와 나머지 문자열의 길이의 합은 항상 i 여야 한다.

(-> 부분 문자열의 길이 x n 이 나머지 문자열의 길이이므로 나누어 떨어져야한다.)

 

즉 abcabcabcabc의 경우 KPM알고리즘을 이용한 idx 는 000123456789 이다.

부분 문자열이 될 수 있으려면, 자신의 길이 이후의 index 에 대해 항상 증가해야 한다.(위의 경우 0~2 까지는 될 수 없다는 뜻) 

이 때, 전체가 될 수 있는 가장 짧은 부분 문자열 길이 3과 나머지 길이 9 의 합은 12이며, 나머지 길이의 합은 idx[last] 와 같아야 한다. 

 

#include <cstdio>
#include <string>
#include <iostream>
#include <cstring>
using namespace std;

char input[1000001];
int findIdx[1000001];

int main() {
	while (1) {
		ios::sync_with_stdio(false);
		cin.tie(0);
		cin >> input;
		if (input[0] == '.') break;
		//KMP making idx array;
		int j = 0;
		int i;
		for (i = 1; input[i]; ++i) {
			while (j && input[i] != input[j]) {
				j = findIdx[j - 1];
			}
			if (input[i] == input[j]) {
				findIdx[i] = ++j;
			}
			else {
				findIdx[i] = 0; 
			}
		}
		//verify
		if (i %(i - findIdx[i-1] )==0) {
			printf("%d\n", i / (i - findIdx[i-1]));
		}
		else {
			printf("1\n");
		}

		
	}
	return 0;
}