RabinKarp1 [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().. 2020. 6. 20. 이전 1 다음