[BOJ] 4354 : Power Strings

문제 : https://www.acmicpc.net/problem/4354

---

문자열처리 KMP

KMP 알고리즘을 활용해 문자열 L 에서 반복되는 구간을 찾는 문제입니다.

 

문자열 L 이 임의의 문자열 T = "xxx" 가 n번 반복되서 만들어졌다고 가정합시다.

그럼 다음과 같은 사실이 무조건 성립합니다.

문자열 L 에서 접두사와 접미사가 같은 최대 길이 = | L | - | T | 

즉, 접두사와 접미사가 최대로 같은 부분은 아래 그림과 같습니다.

따라서, 문자열 L의 최대 접두사와 접미사의 길이를 KMP 알고리즘을 이용해  구하고,

| L | 에서 빼준다면 | T | 를 구할 수 있습니다.

이때, | T | 의 제곱꼴로 | L | 이 이루어졌다면,  | L | % | T | 가 0 이 성립해야합니다.

#include<iostream>
#include<vector>

using namespace std;

vector<int> getPartialMatch(string N) {
	int m = N.size();
	vector<int> pi(m, 0);
	int begin = 1, matched = 0;
	while (begin + matched < m) {
		if (N[begin + matched] == N[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0) begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}
	return pi;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	while (1) {
		string L;
		cin >> L;
		int N = L.length();
		if (L == ".") break;
		vector<int> pi = getPartialMatch(L);
		if (N % (N - pi[N - 1]) == 0)
			cout << N / (N - pi[N - 1]) << '\n';
		else {
			cout << 1 << '\n';
		}
	}
	return 0;
}

---