[백준] 1701: Cubeditor

0. 문제 주소

 

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

1701번: Cubeditor

 

 

1. 풀이

 

KMP 알고리즘에서 사용하는 fail 함수를 이용하는 문제

 

2번 이상은 2번만 나와도 된다는 얘기고, 접두사와 접미사가 같다는 얘기는 동일한 부분 문자열이 2번 나온다는 것과 같다.

 

처음엔 가능한 모든 부분 문자열에 대해 fail 배열을 만들어서 최댓값을 찾게 했는데 TLE를 받았다.

 

당연히 N^3이라 터진다. 생각해보니까 양 끝에서 동일한 개수만큼 문자를 덜어낸 부분 문자열들만 체크해줘도 최댓값을 찾을 수 있었다.

 

어차피 한 문자열에 대해 fail 배열을 만든다는 것은 그 문자열의 첫 번째 글자부터 i번째 글자까지(i는 1부터 끝) 같은 모양의 접두사&접미사의 최대 길이를 구하는 것이기 때문에

 

양 끝을 동일한 개수만큼 제거하며 N번만 보아도 모든 경우를 찾을 수 있다.

 

 

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <bits/stdc++.h>

const int MAX = 5000;

using namespace std;

string K;
int fail[MAX];

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     
    cin >> K;
    int N = K.size();
    int ans = 0;
    for (int k=0;k<N;k++){
        string S = K.substr(k, N-k);
        memset(fail, 0, sizeof(fail));
        for (int i=1, j=0;i<S.length();i++){
            while(j>0 && S[i] != S[j]) j = fail[j-1];
            if (S[i] == S[j]) fail[i] = ++j;
        }
        ans = max(ans, *max_element(fail, fail+N));
    }
    printf("%d\n", ans);

    return 0;
}