接尾辞配列--文字列を処理する利器

接尾辞配列は文字列を処理する強力なツールです.接尾辞配列は接尾辞ツリーの非常に精巧な代替品であり、接尾辞ツリーよりもプログラミングが容易であり、接尾辞ツリーの多くの機能を実現することができ、時間の複雑さも遜色なく、接尾辞ツリーよりもメモリ空間が小さい.
サブストリング:文字列Sのサブストリングr[i..j],i<=jは、rストリングにおいてiからjまでのセグメント、すなわちr[i],r[i+1],...,r[j]を順次配列した文字列を表す.
接尾辞:接尾辞とは、ある位置iから列全体の末尾までの特殊なサブ列を指す.文字列sのi番目の文字から始まる接尾辞は、Suffix(i)、すなわちSuffix(i)=r[i..len(s)]と表される.
サイズ比較:文字列のサイズ比較とは、一般的に「辞書順」の比較である.すなわち、2つの文字列u,vについて、iを1から順にu[i]とv[i]を比較させ、u[i]=v[i]であればiに1を加算させ、そうでなければu[i]v[i]であればu>v(すなわちvlen(u)またはi>len(v)が比較されず結果が得られないと考える.len(u)len(v)するとu>v.文字列のサイズ比較の定義から、Sの2つの先頭位置の異なる接尾辞uとvを比較した結果が等しいはずがない.u=vの必要条件len(u)=len(v)はここでは満たされないからである.
接尾辞配列:接尾辞配列SAは、1.nの配列SA[1],SA[2],......,SA[n]を保存し、Suffix(SA[i])を保証する1次元配列である.
1接尾辞配列最長共通サブ列を求める(LCS)
解法:2つの文字列を1つの特殊な記号(2つの文字列にはなく、例えば‘#’)で接続し、接続後の文字列の接尾辞配列を構築し、接尾辞配列の中で最も長い共通接頭辞を求め、最も長い共通接頭辞が1つの文字列だけに現れるのではなく、元の2つの文字列に現れることを保証する.これが特殊な接続記号の役割である.

#include 
using namespace std;

//  qsort     
int pstrcmp(const void *p, const void *q) 
{     
    return strcmp(*(char**)p,*(char**)q); 
}

//      
int comlen_suff(char * p, char * q) 
{    
    int len = 0;
    int count = 0; //             ‘#’，LCS        ，            
    while(*p && *q && *p++ == *q++)     
    {         
        ++len;         
        if(*p == '#' || *q == '#')
        {
            break;
        }
    }
    while(*p)
    {
        if(*p++ == '#')
        {
            ++ count;
            break;
        }
    }
    while(*q)
    {
        if(*q++ == '#')
        {
            ++ count;
            break;
        }
    }
    if(count == 1)
        return len;
    return 0; 
}   

//      
int LCS(char * X, char * Y) 
{
    char * suff[999];
    int maxlen = 0;
    int suf_index;
    int xlen = strlen(X);
    int ylen = strlen(Y);
    int len_suff = xlen + ylen + 1;     
    char * arr = new char[len_suff + 1];  //  X Y     
    strcpy(arr,X);   
    arr[xlen] = '#';
    strcpy(arr + xlen + 1, Y);       
    for(int i = 0; i < len_suff; ++i)  //        
    {
        suff[i] = &arr[i];     
    }
    qsort(suff, len_suff, sizeof(char *), pstrcmp);    
    for(int i = 0; i < len_suff-1; ++i)    
    {
        int len = comlen_suff(suff[i],suff[i+1]);
        if(len > maxlen)        
        {
            maxlen = len;       
            suf_index = i;   
        }
    }
    printf("%.*s
", maxlen, suff[suf_index]);
    delete[] arr;
    return maxlen;
}

int main()
{
    cout<"aabaaba","aba")<<endl;
    return 0;
}

2接尾辞の配列は最長の文のサブ列を求めます(LPS)
解法:文字列の逆順序と元の文字列を特殊な記号で接続し、接尾辞配列を構築し、接尾辞配列の中の最長の共通接頭辞を求め、最長の共通接頭辞が特殊な接続記号の両端に現れることを保証する.

#include 
using namespace std;

//  qsort     
int pstrcmp(const void *p, const void *q) 
{     
    return strcmp(*(char**)p,*(char**)q); 
}

//      
int comlen_suff(char * p, char * q) 
{    
    int len = 0;
    int count = 0; //             ‘#’，LCS        ，            
    while(*p && *q && *p++ == *q++)     
    {         
        ++len;         
        if(*p == '#' || *q == '#')
        {
            break;
        }
    }
    while(*p)
    {
        if(*p++ == '#')
        {
            ++ count;
            break;
        }
    }
    while(*q)
    {
        if(*q++ == '#')
        {
            ++ count;
            break;
        }
    }
    if(count == 1)
        return len;
    return 0; 
}

//      
int LPS(char * X) 
{
    char * suff[999];
    int maxlen = 0;
    int suf_index;
    int xlen = strlen(X);
    int len_suff = 2 * xlen + 1;    
    char * arr = new char[len_suff + 1];  //  X   X       
    strcpy(arr,X);
    arr[xlen] = '#';
    char *p = X;
    char *q = arr + len_suff;  
    *q = '\0';
    while(*p && (*--q = *p++)); //     
    for(int i = 0; i < len_suff; ++i)  //        
    {
        suff[i] = &arr[i];   
    }
    qsort(suff, len_suff, sizeof(char *), pstrcmp);   
    for(int i = 0; i < len_suff-1; ++i)    
    {        
        int len = comlen_suff(suff[i],suff[i+1]);    
        if(len > maxlen)
        {          
            maxlen = len;
            suf_index = i;
        }  
    }
    printf("%.*s
", maxlen, suff[suf_index]);
    delete[] arr;
    return maxlen;
}

int main()
{
    cout<"aabaab")<<endl;
    return 0;
}

3接尾辞配列最長繰返しサブ列(LRS)を求める
解法:文字列の接尾辞配列を構築し、接尾辞配列を並べ替え、さらに2つ比較して最も長い繰り返しサブ列を得る

//compare funciton used by qsort()
int pstrcmp(const void *p, const void *q)
{
    return strcmp(*(char **)p, *(char **)q);
}

//get max common length of string p and q
int comlen(char *p, char *q)
{
    int len = 0;
    while (*p && (*p++ == *q++))
        len++;
    return len;
}

//get max repeat substring of str 
int find_max_repeat(char* str, char* result, int & len)
{
    int temlen, maxi, maxlen = -1;
    char *a[99999];
    int n = 0;

    while (*str != '\0')
    {
        a[n++] = str++;
    }
    qsort(a, n, sizeof(char *), pstrcmp);
    for (int i = 0; i < n-1; i++)
    {
        temlen = comlen(a[i], a[i+1]);
        if (temlen > maxlen)
        {
            maxlen = temlen;
            maxi = i;
        }
    }
    result = a[maxi];
    len = maxlen;
    printf("%.*s
", maxlen, result);
    return maxlen;
}

4接尾辞の配列は最も長い重複する文字のサブ列を求めます
解法:この文字列に接尾辞配列を構築し、各接尾辞配列の中で、重複文字のない最長接頭辞を探すのが、探すサブ列です.

//                
int longestlen(char * p)
{
    int hash[256];
    int len = 0;
    memset(hash,0,sizeof(hash));
    while (*p && !hash[*p])
    {
        hash[*p] = 1;
        ++ len;
        ++ p;
    }
    return len;
}

//        
int longest_unique_substring(char * str)
{
    int maxlen = -1;
    int begin = 0;
    char *a[99999];
    int n = 0;
    while(*str != '\0')
    {
        a[n++] = str++;
    }
    for (int i=0; i)
    {
        int temlen = longestlen(a[i]);
        if (temlen > maxlen)
        {
            maxlen = temlen;
            begin = i;
        }
    }
    printf("%.*s
", maxlen, a[begin]);
    return maxlen;
}