(백준 4354번 문자열 제곱) (라이님 블로그 대회 알고리즘 따라잡기 31) KMP(Knuth–Morris–Pratt Algorithm)

라이님 블로그에서 아이디어를 가져와서 풀어보았다!

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220917078260&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

KMP 알고리즘(Knuth–Morris–Pratt Algorithm) (수정: 2019-09-01)

늘 그렇듯 설명은 라이님 블로그를 참고!

 

이 문제에서 처음에 틀렸습니다가 뜨면 abcabca를 한 번 넣어보는 걸 추천한다. 정답은 1이지만 2가 나올 가능성이 있기 때문...!

 

이제 좀 KMP 알고리즘이 익숙해지는 중이다! 캬캬

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	string S;
	while (getline(cin, S) && S[0] != '.') {
		int M = S.length();
		vector<int> fail(M, 0);

		for (int i = 1, j = 0; i < M; i++) {
			while(j > 0 && S[i] != S[j]) j = fail[j - 1];
			if (S[i] == S[j]) fail[i] = ++j;
		}

		int n;
		if (M % (M - fail[M - 1]) == 0) n = M / (M - fail[M - 1]);
		else n = 1;
		
		cout << n << "\n";
	}
	return 0;
}