백준 BOJ 4354 - 문자열 제곱

오늘의 KMP 그 두번째 문제

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

4354번: 문자열 제곱

반복되는 가장 작은 문자열의 길이를 https://blog.koderpark.dev/263

1305번 풀이와 동일하게 구해준 다음,

 

( 문자열의 길이 / 반복되는 가장 작은 문자열의 길이 )

로 구해줄 수 있다.

이때, 코너케이스가 있는데, 나눈 나머지를 보는 방법도 있다고 하지만

나는 그냥 입력받은 문자열을 두배로 이어붙여서 나온 값을 다시 2로 나누었다.

이 경우에는 자기 자신 또한 길이 두배 문자열의 접두사 / 접미사가 될 수 있으므로 AC를 받을 수 있다.

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
using namespace std;

int fail[2345678]= {0};

int main(){
	string s;
	while(cin >> s){
		if(s == ".") break;
		s = s+s;
		memset(fail, 0, sizeof(fail));
		
		int N = s.length();
		
		for(int i=0,j=1; j<N; j++){
			while(i && s[i] != s[j]) i = fail[i-1];
			if(s[i] == s[j]) fail[j] = ++i;
		}
		
		int tmp = (N)-fail[N-1];
		
		cout << N/tmp/2 << "\n";
	}
	return 0;
}