[백준] 4354번 : 문자열 제곱 - 자세한 설명 포함 KMP 알고리즘 응용

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

4354번: 문자열 제곱

1.문제설명

 

KMP 알고리즘에 대해 공부하고 예제를 풀던 중

백준 4354번 문자열 제곱 문제를 풀게 되었다.

 

처음에 이 문제를 어떻게 KMP 알고리즘으로 풀 수 있는지 한참 고민했으나

생각이 나지 않아 구글에 여러 블로그를 뒤져보아도

마땅히 명쾌한 설명을 발견하지 못해 더 한참을 고민했다.

 

 

그러다 유튜브를 뒤져보던 중

'개발자영맨' 님의 동영상에서 다음과 같은 KMP 알고리즘의 성질을 발견했다.

말로 설명해주시는 걸 들으면 쉽게 이해할 수 있어서

동영상 31분부터 보면 좋을 것 같다.

 

KMP prefix 특성

출처: https://www.youtube.com/watch?v=OhMFeV8VeAc&t=510s 

 

 

 

실패함수든 lps든 prefix function이든

KMP알고리즘을 사용하기위해

prefix와 suffix를 구하면 그를 통해 반복 패턴의 길이를 구해낼 수 있다.

 

 

즉 이 백준문제에서는 단순히 답을 구하기위해

전체 string의 길이에서 위에서 구한 반복 패턴의 길이를 나누었을 때 나머지가 0으로 나누어 떨어진다면

(답 = 전체 string의 길이 / 반복패턴의 길이) 가 된다.

 

 

 

좀 더 자세히 설명하자면 위의 사진과 동일하게

pattern 문자열 = abababa 로 생각해보면

 

실패함수[n-1] = 5 이고,

전체 string의 길이 = 7 이므로

반복 패턴의 길이는 2 이고

반복 패턴은 ab이며

 

pattern 문자열(abababa)은 반복 패턴 ab가 반복된 모양이 된다.

즉 KMP 알고리즘에서 실패함수를 유도하는 과정에서 pattern에 대한 반복 패턴도 자연스럽게 얻어진다.

 

이러한 성질을 통해 코드를 구현하면 된다.

 

 

 

---

 

 

2.문제풀이코드

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

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

    string s;
    while(1){
        cin >> s;
        if(s==".") break;

        int N = s.length();
        int lps[N];
        memset(lps,0,sizeof(lps));

        //prefix function
        int j = 0;
        for(int i=1; i<N; i++){
            while(j>0 && s[i]!=s[j]){
                j = lps[j-1];
            }
            if(s[i]==s[j]){
                j++;
                lps[i] = j;
            }
        }

        int repeatLength = N - lps[N-1];
        if(N % repeatLength == 0){
            cout << N / repeatLength << '\n';
        }
        else{
            cout << 1 << '\n';
        }
    }

    return 0;
}

백준 4354번