문제

문제 링크

문제 접근

  • 이 문제를 어떻게 KMP로 풀지를 고민하다가 2시간 만에 방법이 퍼뜩 떠올랐다.
  • 2번 이상 존재한다는 것은 부분 문자열 중에 접두사와 접미사가 같은 경우가 있다는 것이고 이 접두사와 접미사가 제일 길게 같은 경우가 정답이라고 볼 수 있다.
  • 즉, KMP에서 찾아냈던 pi값이 가장 큰 경우가 정답이 된다.
  • 여기서 문제는 기존의 make_pi 함수는 부분 문자의 시작은 0이지만 이번에는 0이 아니라 문자열의 처음부터 끝까지이다.
  • 이를 위해 make_pi를 변형해서 답을 구했다.

코드

기존 make_pi()

void make_pi(){
    int j = 0;
    for(int i = 1; p[i] != '\0' ; i++){
        while(j > 0 && p[i] != p[j]) j = pi[j-1]; 
        if(p[i] == p[j]) pi[i] = ++j; 
    }
}

정답 코드

#include <iostream>
using namespace std;
int ans, n, pi[5001];
char t[5001];

int main(){
    cin.sync_with_stdio(false); cin.tie(NULL);
    cin >> t;
    for(int i = 0; t[i] != '\0'; i++){
        int k = 0;
        for(int j = i + 1; t[j] != '\0'; j++){
            while(k > 0 && t[j] != t[i + k]) k = pi[k - 1];
            if(t[j] == t[i + k]){
                k++;
                if(ans < k)ans = k;
            }
            pi[j - i] = k;
        }
    }
    cout << ans;
    
}

느낀점

  • 아무래도 정확하게 개념을 이해하지 못하고 있었는지 접두사를 바꾸는 것만으로도 큰 어려움을 겪었다.(제출만 20번 넘게 했다.)
  • 내가 표현하고자 하는 것이 뭔지 정확히 적고나니 문제점을 찾을 수 있었다.
  • 막 바꾸면서 제출하기보다는 천천히 line by line으로 생각하면서 구현해보자.