백준 9248번 문제 [문제 설명] [문제 풀이] LCP를 구하기 전에 Suffix Array를 구해야 한다. Suffix Array를 구하는 방법은 멘버- 마이어스의 알고리즘을 이용해야 한다. 문제에서 주어진 조건이 문자열의 최대 길이가 50만까지 증가할 수 있고 또한 문자열을 처리하는 함수들은 그 동작 속도가 느린 편이기 때문이다. 멘버-마이어스의 알고리즘은 기수 정렬을 이용한다. banana에 대해서 적용 과정을 보면 b a n a n a \0 index 0 1 2 3 4 5 SA 98 97 110 97 110 97 -1 처음 입력을 받고 SA를 정하면 다음과 같다. (SA의 값들은 ASCII 코드 값을 적은 것임) 이 표의 SA를 가지고 정렬을 수행한다. 같은 값을 가지는 SA들이 문제가 되는데(예를 들면 1,3,5 .. 이전 1 다음
