[C/C++] 백준 - 1701번 : Cubeditor [KMP 알고리즘]

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

1701번: Cubeditor

문제

Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다.

텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 겹쳐도 된다.

예를 들어, abcdabc에서 abc는 두 번 나오기 때문에 검색이 가능하지만, abcd는 한 번 나오기 때문에 검색이 되지를 않는다.

이렇게 어떤 문자열에서 두 번 이상 나오는 부분 문자열은 매우 많을 수도 있다. 이러한 부분 문자열 중에서 가장 길이가 긴 것을 구하는 프로그램을 작성하시오.

예를 들어, abcabcabc에서 abc는 세 번 나오기 때문에 검색할 수 있다. 또, abcabc도 두 번 나오기 때문에 검색할 수 있다. 하지만, abcabca는 한 번 나오기 때문에 검색할 수 없다. 따라서, 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 abcabc이기 때문에, 이 문자열이 답이 된다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 5,000이고, 문자열은 모두 소문자로만 이루어져 있다.

출력

입력에서 주어진 문자열의 두 번이상 나오는 부분문자열 중에서 가장 긴 길이를 출력한다.

---

위 문제는 문자열 S가 주어졌을 때, S내 2번 이상 등장하는 부분문자열 중 가장 길이가 긴 문자열을 구해야한다. 어떻게 해결해야할까

문자열의 최대 길이는 5000이고 시간 제한은 0.5초이다. 완전탐색으로 문제를 해결하려면 주어진 문자열의 모든 부분문자열의 등장 횟수를 세어주어야 하는데 이 방식으로는 시간 내 해결이 불가능하다.

그럼 어떻게 해결해야할까, 문자열 내 부분문자열의 등장, 최적화를 진행한 ---> KMP 알고리즘을 이용해야한다.

 

일반적인 KMP 알고리즘은 탐색 알고리즘으로 String A, B가 있을 때 B가 A문자열 어느 곳에 위치하는지 시작 위치를 반환받는 알고리즘으로 배웠다. 이걸 어떻게 응용해야할까,, 우선 처음에 문제에 주어진 힌트를 분석해봤다.

 

1. 문자열은 하나만 주어진다.

2. KMP 알고리즘은 부분문자열이 전체 문자열 중 어디에 등장하는지 시작 위치를 반환해주는 알고리즘으로 최적화를 위해 접두사이면서 접미사인 최대 문자열의 길이를 구한다.

3. 2번에서 구한 최대 문자열을 통해 해당 문제의 정답이 될 수 있는 문자열의 길이를 구할 수 있지 않을까?

-> 전체 문자열에서 부분 문자열의 형태(=S)로 만들어준 후 S에서 '접두사이면서 접미사인 최대 문자열의 길이(=l)'를 모두 구해준다. 그리고 l의 값을 초기화 해나가며 최대값을 저장해주어야 하는데, 여기서 중요한 점이 최대값의 길이가 된다고 하더라도 문제의 조건 부분문자열의 2번 이상 등장한다는 것을 판단해주어야한다. 따라서, 이 부분에서 KMP 알고리즘을 적용하여 전체 문자열에서 해당 부분 문자열의 등장 횟수를 세어주고 횟수가 2 이상일 때만 초기화를 해준다.

 

 

이해할 수 있도록 코드 주석에 내가 생각했던 걸 적어두었다

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define Mod 1000000007
#define endl '\n'

using namespace std;

string H;

void input(){
    cin >> H;
}

vector<int> getPartialMatch(const string &N){
    int m = N.size();
    vector<int> pi(m, 0);
    int begin = 1, matched = 0;
    while(begin + matched < m){
        if(N[begin+matched] == N[matched]){
            ++matched;
            pi[begin+matched-1] = matched;
        }
        else{
            if(matched==0) ++begin;
            else{
                begin += matched - pi[matched-1];
                matched = pi[matched-1];
            }
        }
    }
    return pi;
}

vector<int> kmpSearch(const string &H, const string &N){
    int n = H.size(), m = N.size();

    vector<int> ret;
    vector<int> pi = getPartialMatch(N);
    int matched = 0;
    for(int i=0;i<n;++i){
        while(matched>0 && H[i] != N[matched]){
            matched = pi[matched-1];
        }
        if(H[i] == N[matched]){
            ++matched;
            if(matched==m){
                ret.push_back(i-m+1);
                matched = pi[matched-1];
            }
        }
    }
    return ret;
}

int solution(){
    int answer = 0;
    for(int i=0;i<H.size();i++){
    	// 부분 문자열로 만들어주기
        string S = H.substr(i, H.size());
        // 부분 문자열 내에서 접두사이면서 접미사인 최대 문자열의 길이를 구한다
        vector<int> pi = getPartialMatch(S);
        for(int j=0;j<pi.size();j++){
        	// 최대 문자열의 길이가 answer보다 클 경우에만 KMP 알고리즘을 적용하여 정답을 최신화할지 결정
            if(answer >= pi[j]) continue;
            // 접두사이면서 접미사인 최대 문자열로 다시 생성한 후
            string hint = S.substr(0, pi[j]);
            // KMP 알고리즘을 적용하여 전체 문자열에서 등장 횟수를 세어준다
            vector<int> cache = kmpSearch(H, hint);
            // 문제 조건에 따라 등장 횟수가 2 이상일 경우 정답 초기화 과정 진행
            if(cache.size() >= 2){
                answer = pi[j];
            }
        }
    }
    return answer;
}

int main(){
    fastio;
    input();
    cout << solution() << endl;

    return 0;
}