레야몬

3033번 가장 긴 문자열과 똑같은 문제라서 같이 풀이됩니다. 1. 문제 알파벳 소문자로 이루어진 길이 L인 문자열의 부분문자열 중, 적어도 한 번은 반복되는 문자열을 '반복 부분문자열'이라고 부르자. 문자열이 주어지면, 가장 긴 '반복 부분문자열'의 길이를 구하는 프로그램을 작성하시오. -1- 문자열의 길이 \(L(1 \leq L \leq 200,000)\)이 주어진다. -2- 문자열의 이루는 L개의 알파벳 소문자들이 띄어쓰기 없이 주어진다. -1- 가장 긴 '반복 부분문자열'의 길이를 출력한다. 만약 '반복 부분문자열'이 하나도 존재하지 않는다면 0을 출력한다. 2. 재정의 문자열에서 두 번 반복해서 나오는 가장 긴 문자열을 구하시오. 3. 해결 방법 Suffix Array에서 LCP를 구한다음 LC..

1. 문제 길이가 50만보다 작거나 같은 문자열이 주어졌을 때, Suffix Array와 LCP Array를 구하는 프로그램을 작성하시오. -1- 알파벳 소문자로만 이루어진 문자열 S가 주어진다. S의 길이는 50만보다 작거나 같다. -1- Suffix Array -2- LCP Array를 출력한다. LCP Array의 첫 값은 항상 'x'이다. 2. 재정의 X 3. 해결방법 맨버-마이아스 알고리즘(Manber-Myers Algorithm), kasai 알고리즘을 이용한다. 4. 실수한 점, 개선할 점 Manber-Myers Algorithm에서 정렬을 일반적인 sort로 구현하면 시간 복잡도가 \(O(nlgn^{2})\)이 되는데 이를 counting sort로 구현하면 \(O(nlgn)\)으로 줄일 ..