4) UpdateClasses(newOrder,class,L)
아이디어를 적용해주기 전에 🤔
(아이디어 ;
그렇다면 어떠한 L에 대해서 2L > size of s 이라면 이 때 반환되는 2L개의 문자열은 적어도 s의 모든 글자를 한번씩은 포함함을 의미합니다. 그렇다면 이 경우에는 반환되는 총 7개의 (각 2L개 문자열) 모두에 접미사가 있을 것입니다. 그런데 해당 함수는 2L개의 문자열이 정렬된 newOrder 을 반환하으로 따라서 2L>size of s 인 경우에 정렬된 접미사의 순서가 new order 에 반환되므로 suffix array 가 성공적으로 가능합니다 !
그렇다면 어떠한 L에 대해서 2L > size of s 이라면 이 때 반환되는 2L개의 문자열은 적어도 s의 모든 글자를 한번씩은 포함함을 의미합니다. 그렇다면 이 경우에는 반환되는 총 7개의 (각 2L개 문자열) 모두에 접미사가 있을 것입니다. 그런데 해당 함수는 2L개의 문자열이 정렬된 newOrder 을 반환하으로 따라서 2L>size of s 인 경우에 정렬된 접미사의 순서가 new order 에 반환되므로 suffix array 가 성공적으로 가능합니다 ! )
먼저 해줘야하는 일이 있습니다.
$ 에서 sortdoubled 가 되어서 각 문자열의 2배 길이까지 정렬이 되었습니다.
a
a
a
a
b
b
$a
a$
aa
ab
ab
ba
ba ($ 앞이 접미사 !)
그렇다면 이제 더 이상 단일 글자를 비교해주는게 아니라 2L개의 문자열끼리 비교한 후 정렬해준 것이 됩니다. 즉 그 말은 class 의 범주가 더 이상 1개인 $,a,b 가 아니라 2L개의 글자들로 구성된 새로운 범주를 만들어야 함을 의미합니다. 새롭게 정렬된 2L개의 개수에 맞는 class 를 반환하는 함수가 UpdateClasses 입니다.
1) n <- size of newOrder
newClass <- array of size n
newOrder 도 결국 총 6개의 문자열을 (각각은 2L개의 글자로 구성) 정렬한 순서이므로 n=6입니다. newClass=[⬜️,⬜️,⬜️,⬜️,⬜️,⬜️,⬜️] 입니다. 이 박스를 이제부터 채워줄 것입니다.
2) newClass[newOrder[0]] <- 0
newOrder[0]=s[6]부터 시작하여 2개 (;2L개 인데 L이 1이므로) ‘$a’ 를 의미합니다.
‘$a’ 는 처음 등장한 범주이므로 0을 배정합니다.
3) for i from 1 to n-1 :
cur <- newOrder[i] , prev <- newOrder[i-1]
mid <- (cur + L) , midPrev <- (prev + L) % n
if class[cur] != class[prev] or class[mid]!=class[midPrev]:
newClass[cur] <-newClass[prev]+1
else:
newClass[cur]<-newClass[prev]
return newClass
하나하나 보면 cur <- newOrder[i] , prev <- newOrder[i-1] 이므로 class[cur] vs class[prev] 는 이전 문자열 (2L개로 구성) 과 현재 문자열(2L개로 구성) 시작 글자를 비교하겠다는 뜻입니다. i=1 이라고 한다면 a$ , $a 에서 a 와 $를 비교하겠다는 뜻입니다.
mid <- (cur + L) , midPrev <- (prev + L) % n
newOrder의 각 인덱스가 L만큼 shift해준 문자열 L개+기존 order 을 의미한다고 할 때 간단하게 newOrder[i] = shift된 L개 + 기존 L개 라고 쓸 수 있습니다.
class[cur] vs class[prev] 을 통해서 현재 인덱스의 shift된 L개의 시작 글자가 이전 (어떠한 범주를 배정받은) 인덱스의 shift된 L개의 시작 글자와 동일한지를 살펴보았습니다.
여기서 끝이 아닙니다.
기존 L개의 글자들도 일치하는지 살펴봐야합니다.
Class[mid] vs class[midPrev] 을 통해서 현재 인덱스의 기존 L개의 시작 글자가 이전 (어떠한 범주를 배정받은) 인덱스의 기존 L개와 시작 글자가 동일한지 확인할 수 있습니다.
가령
aa
ab 에서 shift 된 L개의 시작글자는 이전과 동일합니다. 하지만
aa
ab 기존 L개의 시작 글자가 다르므로 ‘aa’ != ‘ab’ 임을 알 수 있습니다.
UpdateClasses 전체 수도코드, 시간복잡도
suffix array 함수 전체 수도코드,시간복잡도
