[문자열] 접미어 배열 & LCP

[문자열] 접미어 배열 & LCP

// 접미어 배열    suffix array
 
#include <stdio.h>
 
#define Size    100
 
char string[Size] = "banana";
int suffixArray[Size];
int lcp[Size];
int strsize;
 
void init()
{
    int i;
    for (i = 0; i < Size; i++)    {
        suffixArray[i] = i;
        lcp[i] = 0;
    }
}
 
int _strlen(char *str)
{
    int s = 0;
    while (str[s] != '\0')    s++;
    return s;
}
int _strcmp(int first, int second)
{
    while (string[first] != '\0' && string[first] == string[second])    {
        first++;
        second++;
    }
    return string[first] - string[second];
}
 
void makeSuffixArray(int start, int end)
{
    // quicksort
    int left = start, right = end;
    int middle = suffixArray[(start + end) / 2];
    int temp;
 
    while (left <= right)    {
        while (_strcmp(suffixArray[left], middle) < 0)    left++;
        while (_strcmp(middle, suffixArray[right]) < 0)    right--;
 
        if (left <= right)    {
            temp = suffixArray[left];
            suffixArray[left] = suffixArray[right];
            suffixArray[right] = temp;
 
            left++;
            right--;
        }
    }
 
    if (left < end)    makeSuffixArray(left, end);
    if (right > start)    makeSuffixArray(start, right);
}
void makeLCP()
{
    // lcp 배열은 suffixarray 순서대로 이전 접미어와 비교, 가장 긴 공통 접두어 길이를 저장
    int i;
    int cnt;
    for (i = 1; i < strsize; i++)    {
        cnt = 0;
        while (string[suffixArray[i - 1] + cnt] == string[suffixArray[i] + cnt])    cnt++;
        lcp[i] = cnt;
    }
}
 
void printSubset()
{
    int i, j;
    int s, e;
 
    for (i = 0; i < strsize; i++)    {
        s = suffixArray[i];
        for (e = s + lcp[i]; e < strsize; e++) {
            for (j = s; j <= e; j++)    {
                printf("%c", string[j]);
            }
            printf("\n");
        }
    }
}
 
int main()
{
    init();
 
    strsize = _strlen(string);
 
    makeSuffixArray(0, strsize - 1);
    makeLCP();
 
    for (int i = 0; i < strsize; i++)    {
        printf("%d - ", suffixArray[i]);
        for (int j = suffixArray[i]; j < strsize; j++) {
            printf("%c", string[j]);
        }
        printf("   \t%d\n", lcp[i]);
    }
 
    printSubset();
 
    return 0;
}