라빈-카프 [3033]

[1. 문제 설명]

https://www.acmicpc.net/problem/3033

---

[2. 풀이 접근]

완전 탐색으로 접근

• 부분 문자열이 발생할 수 있는 대상은 아래와 같다.
• 부분 문자열의 길이는 1 부터 L-1 까지
• 길이 L-1 부터 발생 할 수 있는 모든 부분 문자열을 모두 확인하여 비교하는 방법
• 라빈-카프 알고리즘 등을 이용하여 문자열 비교를 진행하더라도, O(L²) 의 시간 복잡도 발생

이분 탐색으로 접근

• 길이가 4인 부분 문자열이 2개 이상 존재한다고 했을 때,
• 길이가 3인 부분 문자열의 존재는 굳이 확인하지 않아도 된다.
  "ABCDE"FGH
  "ABCDE"XYZ
  => ABCD 라는 중복 되는 부분 문자열이 있음을 바로 알 수 있다.
• 즉, 중복 되는 부분 문자열이 있을 때, 그 보다 작은 길이의 부분 문자열의 중복 존재 여부를 확인 할 필요는 없다.
• 즉, 라빈-카프 알고리즘을 적용한 완전 탐색의 시간 복잡도를 다음과 같이 개선 할 수 있다.  O(L(logL))

라빈-카프 알고리즘의 적용

• 해시가 충돌한 문자열을 어떻게 복원 할 것인지에 대해서 여러가지 방법이 있을 것인데
• 1) 배열을 이용하는 방법 (hash 값을 index 로 하여, 부분 문자열의 시작 offset 을 저장)
• 2) multilmap 을 이용하는 방법 (hash 값을 key 로 하여, 부분 문자열의 시작 offset 을 저장)
• 두가지 방법 중 어떤 것이 더 낫다 할 수 없다.
  # 해시값을 다양하게 만들기 위해서 mod 값을 크게 하면 1) 방법은 사용 할 수 없음
  # 2) 은 1) 보다 느릴 수 있음.

해시를 만들기 위한 base 값과 mod 의 어떤 조합이 가장 좋을 지 알 수 없음.

그런데, 두가지 풀이 중, 메모리 사용량과 처리 시간은 1) 방법이 모두 더 좋았음.

---

[3. 코드 - vector 를 이용]

---

[3. 코드 - multimap 을 이용]