(JAVA) 백준 4354번 : 문자열 제곱 --- [KMP]

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

4354번: 문자열 제곱

 

안녕하세요.

 

이 문제도 KMP 문제로서, 문자열의 접두사와 접미사의 개수를 활용하는 문제입니다.

 

 

필자도 조금 어려워서 고민고민하다 해설을 참고했습니다...ㅠㅠ

 

 

결론은 그거입니다.

 

 

len : 문자열의 전체 길이

pi 배열 : 0 ~ index까지의 부분 문자열의 접두사와 접미사가 같은 그 문자열의 최대 길이

 

가 있을 때,

 

제곱 n = len / (len - pi[len - 1])

 

 

엥?

 

갑자기 저렇게 보면 모르겠죠? 당연합니다.

 

 

 

무슨 뜻이냐면.

 

pi[len - 1]은 0 ~ index 까지의 문자열의 접두사와 접미사가 같은 그 문자열의 최대 길이 입니다.

즉, abaaba 의 pi[6 - 1] 은 3(aba) 입니다.

 

그럼, ababab와 같이 ab^3(3제곱) 인 경우에는 저 알고리즘을 어떻게 대입시키죠?

 

 

잘 생각해보시면 됩니다.

 

ababab의 pi[6 - 1] 은 4(abab) 입니다.

 

근데 저희는 abab 따위 필요없습니다..! ab를 알아내서 ab가 몇 개 연속되었는지를 확인해야합니다.

 

 

잠만...

ababab 중에서 abab를 제거하면 ab만 남네?

즉, len(6) - pi[6 - 1](4) = 2가 되고, 이는 곧 이 문자열의 최대 제곱이 되는 문자열 입니다.

 

그 이유는, 접두사와 접미사가 같을 때, 겹치는 부분이 있다면

그 겹치는 부분을 제외한 부분이 곧 최대 제곱이 될 수 있는 

제곱수 문자열 입니다.

 

다시 예를들어,

 

                 abababab

접두사       ababab

접미사           ababab

같은 부분       abab

다른 부분   ab        ab

 

그런데, 어차피 접두사와 접미사가 겹친다는 것은, 각각의 남은 부분 또한 겹친다는 것이기 때문에 신경쓸 필요가 없죠.

 

그렇게 해서 ab를 구했다면, abababab는 ab가 몇 개 들어가있는지 알아내야겠죠?

그래서 len(8) / (len(8) - pi[8 - 1](6)) = 8 / 2 = 4

 

4개가 들어있습니다.

 

 

 

하지만, 예외가 있습니다.

문자열의 길이가 홀수인 경우는? 제곱이 될 수 없죠. 문자 하나만 쭉 이어서 제곱이 되는 경우를 제외하곤.

 

이에 대한 예외 처리로, pi[len - 1] 이 1보다 크다면 len % (len - pi[len - 1]) != 0 을 통해 예외 처리를 할 수 있습니다.

 

 

반례) ababa

pi[4] = 3

len = 5

5 % (5 - 3) != 0 이므로, 이는 ababa^1 = ababa 만 가능합니다.

 

반례2) aaaaa

pi[4] = 4

len = 5

5 % (5 - 4) == 0 이므로, 이는 a^5 = aaaaa 만 가능합니다.

 

 

이상입니다.

 

자세한 매커니즘 및 궁금한 사항은 아래 소스코드를 확인해주세요.

 

 

감사합니다.

 

 

 

소스코드

---