(알고리즘) 부분 문자열의 사전 순 정렬.

* 문자열이 주어졌을 때 모든 가능한 부분 문자열을 사전순으로 정렬했을 떄 k번쨰 문자열을 찾아보자. 이떄 중복되는 부분 문자열은 없어야 한다. 예를들어, food의 모든 가능한 ㅂ분 문자열을 사전순으로 정렬하면 다음과 같다.


d,f, fo, foo, food, o, od, oo, ood


과정:

입력 문자열의 모든 접미어 배열에서 모든 접두어를 추출하면 모든 가능한 부분 문자열이 된다. 문자열의 길이는 그 문자열의 모든 접미어의 수오 일치하며, 또한 모든 접두어의 길이와도 일치한다. 예를들어, 'food'의 경우 길이가 4인 문자열인데 4개의 접미어와 4개의 접둥를 가진다.

<접미어를 사전순으로 정렬한 결과>

food, ood, od, d -> d, food, od, ood


'food'의 접두어는 다음과 같다.

f, fo, foo, food

위의 사전순으로 정렬된 4개의 접미어 별로 각각 접두어를 뽑으면 다음과 같다.

• d -> d
• food-> f, fo, foo, food
• od -> o, od
• ood -> o, oo, ood

위 결과를 모두 모으면 다음과 같다.

d, f, fo, foo, food, o, od, o, oo, ood

이것이 'food'의 모든 부분 문자열이다. 그러나 이 결과에는 'o'가 중복되어 있으므로 이것을 제거해야 한다.