[백준 4354] 문자열 제곱 (C++)

4354번: 문자열 제곱

KMP

---

예를 들어 문자열 abcab가 있다고 하자

kmp알고리즘을 사용해서 주어지는 문자열마다 접두사 실패 table을 만들어 준다.

-> {0, 0, 0, 1, 2}

table의 마지막 수는 마지막으로 접두사와 중복되는 문자열의 길이를 의미한다.

-> 2 (ab 중복)

현재 문자열(text)의 크기에서 마지막으로 중복되는 접두사의 길이를 빼준다.

-> 5 - 2 = 3

위 값은 중요하다. 무엇을 의미하는 걸까? 

값 '3'은 문자열에서 중복되지 않는 최대 접두사의 길이가 된다.

abcab에서 처음 abc는 반드시 반복되어야 하는 문자열이 된다는 뜻이다.

 

만약 ababab 문자열이 주어지면 실패 table은 {0, 0, 1, 2, 3, 4} 가 될 것이고 중복되지 않는 최대 접두사의 길이는 2가 된다.

문자열의 길이 6을 2로 나눠보자. 나머지가 0이고 값은 3이 된다.

현재 문자열은 최대 접두사가 반복해서 3번 나타난다는 뜻이 된다.

 

다시 abcab 문자열로 돌아가서 문자열의 길이 5를 최대 접두사의 길이 3을 나눠보자.

나머지가 2가되고 값은 1이된다.

접두사가 1번 반복되지만 최대 접두사가 될 수 없다. 나머지가 2라서 최대접두사의 마지막 2개의 문자를 반복할 수 없기 때문이다.

 

여기까지 실패 table의 마지막 수의 의미, 현재 문자열의 길이에서 마지막 중복 접두사길이를 뺀 값의 의미, 현재 문자열의 길이에서 최대 접두사의 길이를 나눈 나머지와 값의 의미를 알아보았다.

**최대 접두사라는건 내가 그냥 이해하기 쉽게 정한 말이므로 공식 용어가 아닌점을 유의해주세요.

 

따라서 현재 문자열의 길이에서 최대 접두사의 길이를 나눈 나머지에 따라서 답을 구할 수 있게된다.

 

 

접두사를 몇 번 접하니까 숨겨진 의미가 많은것 같아서 신기하다.. 그래서 문제를 포스팅하며 분석하는 과정이 재미있었다.

 

#include <iostream>
#include <cstring>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
using namespace std;
 
string text;
int table[1000001];
 
void solve(){
    cin >> text;
    while(text[0] != '.'){
        int sz = text.size();
        memset(table, 0, sizeof(table));
        int j = 0;
        for(int i = 1; i < text.size(); i++){
            while(j > 0 && text[i] != text[j]) j = table[j-1];
            if(text[i] == text[j]) table[i] = ++j;
        }
        
        int div = sz - table[sz-1];
        if(sz % div) cout << 1 << "\n";
        else cout << sz / div << "\n";
        
        cin >> text;
    }
}
 
int main(){
    fastio
    solve();
    
    return 0;
}