접미사 배열 (Suffix Array) & 맨버-마이어스 (Manber-Myers)

접미사 배열 (Suffix Array)?

• 어떤 문자열 S (아래의 경우 "alohomora") 의 모든 접미사를 사전순으로 정렬해 둔 자료구조이다.
• 접미사들을 그대로 문자열 배열에 저장하면 문자열 길이의 제곱에 비례하는 메모리가 필요하기 때문에, 보통 각 접미사의 시작 위치를 담는 정수 배열로 구현된다.

i	A[i]	S[A[i]]
0	8	a
1	0	a l o h o m o r a
2	3	h o m o r a
3	1	l o h o m o r a
4	5	m o r a
5	2	o h o m o r a
6	4	o m o r a
7	6	o r a
8	7	r a

• 접미사 배열을 이용한 문자열 검색의 핵심은 '짚더미 H'가 '바늘 N'을 포함한다면 항상 N은 H의 어떤 접미사의 접두사라는 점을 이용한다.

ex) "alohomora"에서 "homo" 찾기

• "homo"는 "homora"의 접두사가 된다.
• 이 속성을 이용하면 H의 접미사 배열을 이진 탐색해서 각 문자열이 출현하는 위치를 찾을 수 있다.
• 접미사 배열의 길이는 항상 |H|이므로 이진 탐색의 내부는 O(log H) 번 수행된다.
• 각 문자열 비교에 O(N) 시간 복잡도를 가지기 때문에 이진 탐색 수행 시간은 O(N * log H) 를 가진다.
• 하지만 두 문자열을 비교하는 데는 최대 두 문자열의 길이에 비례하는 시간이 걸리므로, 한 번 비교에 O(N) 시간이 걸린다.
• 따라서 전체 시간 복잡도는 O(N^2 * log H) 을 가진다.
• 하지만, "aaaa...aaa" 같은 문자열이 주어진다면 모든 비교가 문자열 끝까지 이루어지기 때문에 많은 시간이 걸릴 것이다.
• 접미사 배열을 구하는 알고리즘 중 O(N)의 시간 복잡도를 가지는 것이 있지만 너무 복잡하여 PS (Problem Solving) 에서는 잘 사용되지 않는다고 한다.
• 따라서, O(N * (log N)^2)의 시간 복잡도로 낮추는 맨버-마이어스 (Manber-Myers) 알고리즘을 사용한다.

 

맨버-마이어스 (Manber-Myers) ?

• 문자열들이 모두 공통된 한 문자열의 접미사라는 점을 이용하여, 기수 정렬 (첫 1글자, 2글자, 4글자, ..., 2^n 글자를 기준으로 정렬) 을 이용한 알고리즘이다.
• 이렇게 log N 번 정렬을 하고 나면 원하는 접미사 배열을 얻을 수 있다.
• 아래 그림은 문자열 "mississipi"의 접미사들을 1, 2, 4, 8 글자를 보고 정렬했을 때의 결과를 보여준다.
• 이렇게 정렬은 여러 번 하는데도 더 빠르게 동작하는 이유는 이전 정렬에서 얻은 정보를 이용해 두 문자열의 대소 비교를 O(1) 에 할 수 있기 때문이다.

 

 

Reference

• https://www.crocus.co.kr/613
• https://ko.wikipedia.org/wiki/%EC%A0%91%EB%AF%B8%EC%82%AC_%EB%B0%B0%EC%97%B4
• https://jason9319.tistory.com/141
• https://www.youtube.com/watch?v=zqKlL3ZpTqs