티스토리 뷰

오늘의 포스팅은 특정문자열에서 반복적으로 나타나는 부분문자열을 찾는 방법입니다.

 

우선 여기서 말하는 반복부분문자열이란 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는)

 

부분문자열을 '반복 부분문자열'이라고 부르겠습니다.

 

예를들어 banana가 있을경우 반복부분 문자열은 an, na, ana 입니다. 

 

머리로는 알겠지만 알고리즘으로는 이를 어떻게 알수 있을까요?

 

방법은 접미사배열(Suffix Array)을 사용하는겁니다.

 

우선 접미사배열이란 전산학에서 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다.(위키백과)

 

예를들어 banana가 있을경우 접미사배열은 다음과 같습니다.

 



다음과 같이 앞에서부터 한칸씩 나가면서 문자열을 잘라냅니다.

 

그리고 이렇게 잘라낸 문자열들을 정렬하면 다음과 같습니다.

 

이게바로 접미사배열! 하지만 이정보만 가지고는 반복부분문자열을 찾기에는 부족합니다.

 

그래서 필요한 개념이 LCP(Longest Common Prefix) 입니다.

 

LCP의 뜻은 가장 긴 공통 접두사로 그 길이에 의미가 있고, SuffixArray를 이용해서 구할수 있습니다. 

 

 

여기서 LCP[i]는 SuffixArray의 i번째 접미사와 i−1번째 접미사의 가장 긴 공통 접두사의 길이 입니다.

 

anana의 LCP값의 경우 3이고 이는 anana의 처음부터 3번째까지가 반복 부분문자열이라는 뜻입니다. 


그리고 LCP의 값이 가장 큰 것이 바로 해당 문자열에서 가장 긴 반복 부분문자열의 길이입니다. 

 

banana의 경우는 LCP가 3인 anana의 3번째인 ana가 반복 부분문자열중 가장 긴 문자열이라는 뜻입니다.

 

이를 이용해서 다음과 같은 문제들을 풀수 있습니다.

 

http://www.acmicpc.net/problem/1605

 

누군가에게는 작은도움이 되었기를 바라면서 오늘의 포스팅 끝~

댓글