[BOJ] 3033 가장 긴 문자열

3033번: 가장 긴 문자열

문제

상근이는 꿈에서 길이가 L인 문자열을 외웠다.

꿈에서 깬 상근이는 이 문자열을 종이에 적었다. 종이를 적던 중에 어떤 문자열은 두 번 이상 등장하는 것 같은 느낌을 받았다.

문자열이 주어졌을 때, 두 번 이상 등장한 부분 문자열 중 가장 길이가 긴 것을 찾는 프로그램을 작성하시오. (부분문자열은 겹쳐서 등장할 수도 있다)

입력

첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다.

출력

첫째 줄에 두 번 이상 등장하는 부분 문자열 중 길이가 가장 긴 것의 길이를 출력한다. 만약 그러한 문자열이 없을 때는 0을 출력한다.

---

처음으로 푸는 백준 플레 문제다. 이번 삼성 특강 문제를 풀면서 처음으로 라빈 카프 알고리즘이라는 것을 알게되고 알고리즘에 익숙해지기 위해서 풀어봤다.

그리고 이 문제는 어제 풀었던 문제처럼 매개 변수 탐색이 쓰인다. 가장 긴 문자열의 길이가 얼마나 되는지 알 수 없기 때문에 대충 이 정도니? 하고 길이를 정한 다음에 실제로 그 길이의 문자열이 2개 존재하는지 확인해본다.

 

이때 제한 시간 안에 문자열을 검사하기 위해서는 해쉬 값을 O(1)에 구해야 한다. 처음 해쉬 값은 문자열 인덱스 0 부터 mid까지의 부분 문자열의 해쉬 값을 저장한다. 이후 이전 해쉬 값을 사용해서 다음 해쉬 값을 구한 다음, 그 해쉬 값이 이전에도 나온 적이 있다면 그 해쉬 값이 나왔던 인덱스들에서 문자열 검사를 실시한다. 이때 실제로도 같은 문자열이 있다면 문자열이 두 번 이상 등장했다고 판단하고 이분 탐색 범위를 조정한다.

 

문제는 잘 푼 것 같은데 자꾸 이상한 값이 나오거나 아예 코드가 터졌다. 첫번째 문제는 해쉬 값을 구할 때 나는 단순히 MOD로 나눈 나머지로 사용했었는데 그렇게 되면 int 값의 범위를 넘어서면서 벡터 인덱스로 음수 값이 들어갈 때도 있었다. 그래서 해쉬 값이 음수로 떨어지는 경우도 처리가 필요했다. 두 번째 문제는 문자열을 비교하는 과정에서 인덱스를 잘못 썼었다. 그래서 for문을 범위 기반 for문으로 다시 썼다. 범위 기반 for문은 처음 사용해봤는데, 익숙해진다면 좋은 도구일 것 같다.

 

 

후기)

사실 이 문제는 혼자 풀지는 못 했고 다른 사람들의 블로그를 참고해서 풀었다. 처음 공부한 알고리즘이다보니 익숙하지 않아서 쉽게 풀 수 없었다. 대략 가닥을 잡았다고 해도 디테일에서 미숙한 게 티가 많이 났다. 해쉬랑 좀 더 친해져야겠다.