접미사 배열(Suffix array) 개념과 예제

1. 접미사 배열
    1-1. 개념
    1-2. 예제
2. LCP
    2-1. 개념
    2-2. 예제
3. 그래서 이걸 어디다 써먹을 수 있는데?

 

 

 

---

 

 

1. 접미사 배열

1-1. 개념

• 접미사
  • 어떤 낱말 뒤에 붙어 다른 낱말을 이루는 말을 뜻한다.
  • ex) 임금님, 사장님, 의느님   ->   '-님'이 접미사

 

• 접미사 배열(Suffix Array)
  • 어떤 문자열의 모든 접미사를 사전 순으로 나열한 배열
  • LCP와 주로 같이 쓰인다.

 

 

2-2. 예제

 

mommy의 접미사 종류

 

mommy라는 문자열로 예시를 들어보자

우선 접미사의 종류를 만든다.

-y

-my

-mmy

이런 식으로!

 

 

접미사 배열 만들기

 

접미사가 들어있는 배열을 사전순으로 나열한 것을 '접미사 배열'이라고 부른다.

우측 표는 접미사 배열이 완성된 모습이다.

 

접미사는 보기 편하게 우측 정렬로

접미사 배열은 비교가 쉽게 좌측 정렬을 하였다.

 

 

2. LCP

2-1. 개념

• LCP(Longest Common Prefix)
  
  • 두 접미사의 가장 긴 공통 접두사
  • 접미사 배열과 주로 같이 쓰인다.

 

• 접두사
  • 어떤 낱말앞에 붙어 다른 낱말을 이루는 말을 뜻한다.
  • ex) 맨주먹, 맨손, 맨얼굴   ->   '맨-'이 접두사

 

2-2. 예제

mommy
my

위 두 접미사의 가장 긴 공통 접두사는 무엇일까?

맨 앞에 문자부터 비교해보면 된다.

첫 번째 문자는 둘 다 'm'으로 같고

두 번째 문자는 'o'와 'y'로 다르다.

즉 LCP는 'm'이 된다.

 

ababc
abc

위 두 접미사의 가장 긴 공통 접두사는 무엇일까?

첫 번째 문자는 둘 다 'a'로 같고

두 번째 문자는 둘 다 'b'로 같고

세 번째 문자는 'a'와 'c'로 다르다.

즉 LCP는 'ab'가 된다.

 

LCP 배열

 

위 표는 접미사를 2개씩 짝지어 LCP를 구해 작성한 표다.

LCP의 첫 번째 값은 0으로 고정하고

mmy와 mommy의 LCP를 두 번째 값에 적고

mommy와 my의 LCP를 세 번째 값에 적는 순서이다.

 

 

3. 그래서 이걸 어디다 써먹을 수 있는데?

SW Expert Academy

 

위 문제는 부분 문자열을 사전 순서대로 나열했을 때 K번째에 오는 문자열을 묻는 문제이다.

완전 탐색을 이용해 모든 부분 문자열을 구할 수 있지만 꽤 느린 속도를 보여준다.

이때, 접미사 배열과 LCP를 이용하면 포문을 많이 돌리지 않아도 수학적인 접근으로 쉽게 답을 얻어낼 수 있다.

 

자주 나오는 알고리즘 문제 유형은 아니지만 알아두면 꽤 효율적인 실행 속도를 보여주니 알아두면 좋을 것 같다.

 

 

(문제 해석 및 풀이 링크 첨부 예정)

 

 

 

---

📘 참고한 자료

• 라이님 블로그 (접미사에 대해 엄청 자세히 깊게 파고든 글)

---