[leetcode][1044] Longest Duplicate Substring

문제 : https://leetcode.com/problems/longest-duplicate-substring/

---

문자열 S가 주어지면 두 번 이상 발생하는 S의 모든 중복 된 하위 문자열들 중 가장 긴 문자열을 찾아라.

---

binary search 로 정답이 가능한 하위 문자열 길이 범위를 줄여나간다. 

length를 문자열 길이의 하위 문자열이 문자열 S에 두 번 이상 발생하는지 확인할 때는 Rabin-Karp 알고리즘을 사용한다.

 

라빈 카프 알고리즘은 해시 기법을 사용한다.

문자열이 같은지 비교할 때 1차로 해시가 같은지 비교하고, 해시가 같을 때만 실제로 문자열이 같은지 비교한다.

자바에서 hashCode(), equals() 함수를 생각하면 이해하기 쉽다.

객체를 비교할 때 1차로 hashCode() 리턴 값을 비교하고 같은 경우 equals() 함수로 객체가 같은지 비교한다.

 

해시 값은 문자열들의 26^(자리수-1) * (문자 - 'a' + 1) 의 합으로 사용했다. 해시 값을 최대한 안 겹치게 만들어야 문자열의 실제 비교도 적게 발생하므로 해시 값이 중요하다.

문자열의 길이 제한이 10^5 이기 때문에 해시 연산 시 모듈러 연산으로 자료형 범위를 넘지 않게 조심한다.

이런 해시 값을 key값, 문자열의 시작 인덱스 배열을 value 값을 하는 map을 만든다.

length를 길이로 하는 하위 문자열들을 구하면서 이 map에 저장하는데 저장하기 전에 같은 해시 값을 가지는 문자열들이 있다면 간단히 == 연산으로 두 개의 문자열이 같은지 비교한다. 같다면 해당 문자열이 정답이 가능한 하위 문자열이 된다.

 

이렇게 length를 하위 문자열의 길이로 가정하고 정답이 가능한지 체크한다음 정답이 가능하다면 해당 문자열을 정답으로 갱신한뒤 binary search 탐색 범위가 [l, r]이었다면 [length+1, r]로 갱신한다. (가장 긴 문자열을 찾아야하기 때문에 length 보다 긴 문자열로 정답이 가능한지 찾아야 한다. 만약 length가 정답이 불가능하다면 [l, length-1]로 갱신한다.

 l <= r 인 경우 위 알고리즘을 반복하고 l > r 가 되었을 때 종료한다.

 

N = 문자열 S 길이라고 했을 때, 시간복잡도는 binary search에 O(logN). length로 정답이 가능한지 Rabin-Karp 알고리즘으로 찾는데 O(N) 정도 소요되므로 O(NlogN) 이다. Rabin-Karp 는 해시 값의 충돌이 많이 발생할수록 문자열의 실제 비교가 더 많이 발생하므로 해시값을 어떻게 잡는지, 충돌이 얼마나 발생하는지에 따라 실행시간은 달라질 수 있다.

 

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/1044.%20Longest%20Duplicate%20Substring.cpp

---

로직상 TLE 발생할게 없는데 계속 TLE가 발생해서 코드를 계속 보고 보고 또 보니까 map을 사용중이었다.

순서가 상관없는 map을 사용하는 경우는 unordered_map을 사용하자.. 평소 시간복잡도가 map은 O(logN), unordered_map은 O(1)이다. (참고) 보통 문제들이 시간이 그렇게 타이트하지 않아서 그냥 map 사용했는데 여기서 그 습관이 오늘의 최대 스트레스의 원인이 됐다. 저녁 간단하게 먹으려고 했는데 당 땡겨서 맛난것좀 먹어야겠음.