백준 1701번: Cubeditor (C++)

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

1701번: Cubeditor

---

Solved By: KMP

 

주어진 문자열 S에서 2번 이상 반복되는 부분 문자열 중 최대 길이를 찾아야 합니다.

 

즉, 2번만 반복되어도 문제의 조건을 만족합니다.

이 점을 이용하여 KMP에서 pattern의 prefix와 suffix의 최대 일치 길이를 구하는 방법을 사용해봅시다.

이 방법을 사용하는 이유는 pattern이라는 문자열에서 prefix와 suffix가 얼마큼 같은지에 대한 길이를 알 수 있기 때문입니다.

그리고, prefix와 suffix, 2개이기 때문에 문제의 조건을 만족하기 때문입니다.

 

문제 예제 1번처럼 "abcdabcabb"가 주어졌다고 해봅시다.

그럼 getPi(pattern의 prefix와 suffix의 최대 일치 길이를 구하는 방법)함수를 사용했을 때,

 

"abcdabcabb"

부분 문자열의 길이를 늘려가면서 부분 문자열의 길이가 7일 때 (index == 6), prefix와 suffix의 최대 일치 길이를 가진다고 볼 수 있습니다.

 

그럼 문제를 다 풀었다고 할 수 있을까요? 아닙니다.

다음과 같은 데이터는 어떨까요.

 

"abbcbbad"

getPi를 사용했을 때, 최대 일치 길이는 1을 반환할 겁니다.

prefix와 suffix만 가지고서 놀기 때문입니다. -> "abbcbbad"

 

하지만, 눈으로 보아도 답은 "abbcbbad"입니다. 이렇게 구하지 못 하는 이유는 "bb"는 prefix라 할 수 없기 때문입니다.

 

prefix가 되려면 문자열은 "abbcbbad"가 아닌 앞에 a가 사라진 "bbcbbad" 문자열의 형태를 가져야 하니까요.

 

[Solution]

즉, 이번 문제의 솔루션은 prefix의 조건을 만족시키기 위해 S의 시작점 인덱스를 하나씩 증가시킨 부분 문자열에서 getPi를 돌려서 해당 부분 문자열에서의 0 ~ i 부분 문자열들의 prefix와 suffix의 최대 일치 길이를 구하여야 한다는 것을 알 수 있습니다.

 

S의 substring들의 substring에서 prefix와 suffix의 최대 일치 길이

"abbcbbad" -> "abbcbbad" = 1

"bbcbbad" -> "bbcbbad" = 2

"bcbbad" -> "bcbbad" = 1

"cbbad" -> "cbbad" = 0

...

>> 여기 나오는 값들 중 최댓값을 구하면 됩니다.

 

핵심은 최소 2번 이상이므로 prefix와 suffix를 떠올리는 아이디어와 prefix의 조건을 생각해보았을 때, S의 부분 문자열들에서 getPi를 사용하는 아이디어를 떠올리면 풀 수 있습니다.

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

vector<int> getPi(string p){
    vector<int> pi(p.size(), 0);
    
    for(int i = 1, j = 0; i < p.size(); i++){
        while(j > 0 && p[i] != p[j]) j = pi[j - 1];
        if(p[i] == p[j]) pi[i] = ++j;
    }
    
    return pi;
}

int main(){
    string s;
    cin >> s;
    
    int result = 0;
    for(int i = 0; i < s.size() - 1; i++){
        auto pi = getPi(s.substr(i, s.size()));
        
        int temp = 0;
        for(auto subpi : pi){
            temp = max(temp, subpi);
        }
        
        //cout << temp << '\n';
        result = max(result, temp);
    }
    
    cout << result;
}