[백준 1701] Cubeditor (C++)

1701번: Cubeditor

KMP

---

문자열의 길이가 5,000이라서 O(N^2) 시간이 가능하다.

 

kmp알고리즘은 text문자열과 pattern문자열이 주어지고,

pattern문자열에서 text 문자열의 접두사가 몇 번 나오는지, 나올때마다 접두사의 몇 번째 문자열까지 나오는지 알 수 있다.

text문자열을 pattern으로 써서 일명 jump table 이라고 하는걸 만들 수 있는데 jump table의 특성을 생각해보면 문제를 해결할 수 있다.

 

위 그림을 보면 'ababcabc'라는 문자열이 있는데 해당 문자열의 jump table은 

0 0 1 2 0 1 2 0 이다.

 

두번째 'a'가 나올 때 접두사 'a'와 같기 때문에 table에 1이 들어간다.

이어서 두번째 'b'가 나오게 되고 접두사'a'를 방금 찾았으므로 접두사 'a'의 다음인 'b'를 봤을 때 둘은 같게된다.

따라서 이전 table값인 1에  1을 더한 2가 들어간다.

그리고 'c'가 나오게 되고 접두사의 그 다음 문자는 'a'이다. 서로 다르기 때문에 접두사를 되돌아 가면서 'c'가 있는지 확인한다.

끝까지 돌아갔음에도 'c'가 없으므로 table에는 0이 들어간다.

 

jump table에 입력된 숫자들은 접두사와 연속으로 일치하는 문자열의 길이를 뜻한다.

따라서 table에서 가장 큰 숫자가 접두사와 일치하는 문자열의 최대 길이이다.

 

처음에 O(N^2)시간이 가능하다고 했으므로 주어진 문자열의 첫 부분을 하나씩 빼면서 KMP알고리즘을 수행한다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
string text;
int table[5001];
 
int KMP(string pattern){
    memset(table, 0, sizeof(table));
    int res = 0;
    int j = 0;
    
    for(int i = 1; i < pattern.size(); i++){
        while(j > 0 && pattern[i] != pattern[j]){
            j = table[j-1];
        }
        if(pattern[i] == pattern[j]){
            table[i] = ++j;
        }
        res = max(res, table[i]);
    }
    return res;
}
 
void solve(){
    int res = 0;
    for(int i = 0; i < text.size(); i++){
        res = max(res, KMP(text.substr(i)));
    }
    cout << res << "\n";
}
 
int main(){
    cin >> text;
    solve();
    
    return 0;
}