BOJ 1701 Cubeditor(Editor)

구하는 것은 간단하다.
입력으로 주어진 문자열에서 어떤 부분 문자열을 검색해서 두 번 이상 나오는(일부가 겹쳐도 된다.) 부분 문자열 중에서 가장 긴 길이를 구하는 문제이다. 

두 번 이상 나오는 문자열 중에서 가장 긴 길이를 구하는 것이므로, 두 번 나오는지만 파악하면 된다. 그러면 생각나는 것이 있다. prefix와 suffix가 같은 부분 문자열 중 최대의 길이를 저장하는 pi배열을 생각했는데, 더 생각해보니 아니다. 모든 prefix에 대해 pi를 구한 것으로는 중간에 두 번 등장하는 부분 문자열을 커버할 수 없다. 그렇다면 모든 부분 문자열에 대해 pi배열을 구하면 가능하겠지만 경우의 수가 너무 많을 것이다.

다시 생각해보자.
결국 백준님의 풀이를 봤다. 좀 충격이었다. 내가 위에서 생각했던 것처럼 정말 모든 부분 문자열에 대해 pi배열의 값을 구해서 그 중 최대값을 구한다. 나는 막연히 경우의 수가 많아 안될 것이라 생각했고 모든 부분 문자열을 어떻게 구해야할지도 몰랐는데, 모든 부분 문자열을 구하는 것은 생각보다 간단하다.

핵심 아이디어는 이것이다. (출처 : 백준님 강의 자료)
모든 부분 문자열은 어딘가에서 시작해서 어딘가에서 끝난다.
즉 어떤 suffix의 prefix가 된다.
pi배열을 구하되, 문자열의 모든 suffix에 대해서 pi배열을 구하면 모든 부분 문자열에 대한 pi배열의 값을 얻을 수 있는 것이다!!
그리고 문자열의 길이는 최대 5000이므로 O(N제곱)의 시간복잡도로도 충분하다.

추가) suffix array와 lcp(longest common prefix)를 이용해서도 가능하다. (더 빠름)