TIL 002 Suffix array (SA)

📕 Suffix array (SA)

👉 사용목적
문자열을 사전 순으로 나열한 배열로, 문자열 문제를 풀 때 사용.
문자열을 담는게 아니라, 문자의 시작 index를 담는다.

예를 들면 camel의 부분 문자열은 camel, amel, mel, el, l 이고, 이를 사전 순으로 나열하면 amel, camel, l, mel,el 이다.

👉 구현
여러방법이 있지만, 9249번을 통과하려면 O(N(logN)^2)의 알고리즘이 필요했다.(대회에서 통용되고 있다고함)

간략하게 말하면, 일단 첫 째 글자로 정렬을 해 그룹을 나눈뒤, 그 후 같은 그룹에 접미사를 d=1 부터 시작해서, d*2 번 째 글짜만 비교를 해서 그 그룹을 안을 정렬을 하는 것이다.

이 때 d*2번째 단어도 단어의 접미사로 어떤 그룹에 속해있음으로, 단어를 비교하는게 아니라 그룹을 비교하는 것만으로도 순서를 정할 수 있다.

ex) banana

• 첫 번째 글자로 정렬
  
• d=1 번째 글짜로 정렬, 글자 수가 초과한다면 짧은 단어를 앞으로(a,anana)
  
• d*2 번째 글자로 정렬, 이 때 글자를 비교 하는게 아니라 ana의 a가 anana의 ana 보다 앞선 그룹에 속해있음으로 앞으로
  
• 그룹 수가 접미사 수가 되면 종료
  

아래 블로그에 설명이 아주 자세히 되어있다.

👉 링크
접미사배열
https://blog.naver.com/kks227/221028710658

👉 팁
파이썬에서 아래처럼 custom compare 함수를 만들어서 넘기는 것보다,

def cmp(i,j):
    if pos[i] != pos[j]:
        return pos[i] - pos[j]
    i += d
    j += d
    if i <n and j <n :
        return pos[i] - pos[j]
    else:
        return j - i

sa.sort(key=cmp_to_key(cmp))

미리 계산한 뒤 sort시키면 훨씬 시간을 단축 시킬 수 있었다.

def getGroup(x):
        if x < n:
            return pos[x]
        else:
            return -1

sa.sort(key=lambda x: (getGroup(x), getGroup(x + d)))