LCS(サブストリングは連続する必要があります)

原文:http://www.ahathinking.com/archives/122.htmlああ、このシリーズはいいですね.お勧めします.
このLCSは前述の最長共通サブシーケンスのLCSとは異なるが、LCSの変体でもあり、LCSではサブシーケンスは連続を要求する必要はなく、サブ列は「連続」である.次のようになります.
題:2つの文字列X,Yを与えて、両者の最も長い共通のサブ列を求めて、例えばX=[aaaba]、Y=[abaa].両者の最長共通サブストリングは[aba]であり,長さは3であった.
このセクションでは、3つの異なる実装方法を示し、各方法の複雑さを比較分析します.内容は次のとおりです.
==基本アルゴリズム==
=DPスキーム==
==接尾辞配列==
==各方法の複雑度分析==
==================================
きほんアルゴリズム
実は最も長い公共の子列に対して、やはり比較的に簡単で考えやすくて、子列が連続しているため、これはとても便利です.最も直接的な方法は,Xの各サブストリングとYの各サブストリングを比較し,最も長い共通サブストリングを求めることである.コードは次のとおりです.

/*        Longest Common Substring */
 
int maxlen;    /*            */
int maxindex;  /*           1      */
void outputLCS(char * X);  /*   LCS */
 
/*             */
int comlen(char * p, char * q)
{
    int len = 0;
    while(*p && *q && *p++ == *q++)
    {
        ++len;
    }
    return len;
}
 
void LCS_base(char * X, int xlen, char * Y, int ylen)
{
    for(int i = 0; i < xlen; ++i)
    {
        for(int j = 0; j < ylen; ++j)
        {
            int len = comlen(&X[i],&Y[j]);
            if(len > maxlen)
            {
                maxlen = len;
                maxindex = i;
            }
        }
    }
    outputLCS(X);
}

==================================
DP方式
最長共通サブストリングが最長共通サブシーケンスの変形である以上、最長共通サブストリングも動的計画で解くことができるのではないでしょうか.
私たちはやはり以前のように「後から前へ」この問題を分解できるかどうかを考えていますが、最も大きなサブ配列和の中で、配列問題については、「arr[0,...i]の問題をarr[0,...i-1]の問題を解く方法に転換するか」を考えることができ、最も長い共通サブ配列の分析に似ています.ここでは、dp[i][j]を用いてx[i]とy[j]で表されています末尾の最長共通サブストリングの長さは、サブストリング連続を求めるため、X[i]とY[j]にとって、以前の共通サブストリングと新しい共通サブストリングを構成するか、または、公共のサブストリングを構成しないか.ゆえにじょうたいてんいほうていしき
X[i] == Y[j],dp[i][j] = dp[i-1][j-1] + 1
X[i] != Y[j],dp[i][j] = 0
初期化の場合、i=0またはj=0であり、X[i]==Y[j],dp[i][j]=1の場合.そうでなければdp[i][j]=0です.
コードは次のとおりです.

/*        DP */
int dp[30][30];
 
void LCS_dp(char * X, int xlen, char * Y, int ylen)
{
    maxlen = maxindex = 0;
    for(int i = 0; i < xlen; ++i)
    {
        for(int j = 0; j < ylen; ++j)
        {
            if(X[i] == Y[j])
            {
                if(i && j)
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                if(i == 0 || j == 0)
                {
                    dp[i][j] = 1;
                }
                if(dp[i][j] > maxlen)
                {
                    maxlen = dp[i][j];
                    maxindex = i + 1 - maxlen;
                }
            }
        }
    }
    outputLCS(X);
}

==================================
接尾辞配列
接尾辞配列の基本的な定義は,サブストリングに関係しており,この方面の考え方を試みることができる.接尾辞配列は最も典型的には1つの文字列の重複するサブ列を探すので、2つの文字列に対して、私たちはそれを一緒に接続することができて、あるサブ列sがそれらの共通のサブ列であれば、sは必ず接続後の文字列の接尾辞配列の中で2回現れて、このように最も長い共通のサブ列を最も長い重複するサブ列に変える問題があります.ここでの接尾辞配列は基本的な実装方式を用いる.
なお、2つの重複するサブストリングが見つかった場合、必ずしもXとYの共通のサブストリングではなく、XまたはYの自身の重複するサブストリングである可能性もあるため、接続時にXの後ろに特殊な文字'#'、すなわち接続後X#Yを挿入する.これにより,見つかった2つの繰返しサブストリングだけがちょうど#の前にあり,この2つの繰返しサブストリングこそXとYの共通サブストリングである.
コードは次のとおりです.

/*             */
char * suff[100];
 
int pstrcmp(const void *p, const void *q)
{
    return strcmp(*(char**)p,*(char**)q);
}
 
int comlen_suff(char * p, char * q)
{
    int len = 0;
    while(*p && *q && *p++ == *q++)
    {
        ++len;
        if(*p == '#' || *q == '#')
        {
            return len;
        }
    }
    return 0;
}
 
void LCS_suffix(char * X, int xlen, char * Y, int ylen)
{
    int suf_index = maxlen = maxindex = 0;
 
    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;
        }
    }
    outputLCS(suff[suf_index]);
}
//                  LCS          。

/*   LCS
 *         ，maxindex=0
 *             suff[]， 0  maxlen   
 */
void outputLCS(char * X)
{
    if(maxlen == 0)
    {
        printf("NULL LCS
");
        return;
    }
    printf("The len of LCS is %d
",maxlen);
 
    int i = maxindex;
    while(maxlen--)
    {
        printf("%c",X[i++]);
    }
    printf("
");
}
 
void main()
{
    char X[] = "aaaba";
    char Y[] = "abaa";
 
    /*      */
    LCS_base(X,strlen(X),Y,strlen(Y));
 
    /* DP   */
    LCS_base(X,strlen(X),Y,strlen(Y));
 
    /*        */
    LCS_suffix(X,strlen(X),Y,strlen(Y));
}

==================================
各シナリオの複雑度の比較
文字列Xの長さをm,Yの長さをn,最長共通サブストリング長をlとする.
基本アルゴリズムでは,Xのサブストリング(m個)とYのサブストリング(n個)を1対1で比較し,最悪の場合,複雑度はO(m*n*l),空間複雑度はO(1)である.
DPアルゴリズムでは,最適サブ問題の解をボトムアップから構築するため,時間的複雑度はO(m*n)である.空間複雑度はO(m*n)であり,もちろんここではスクロール配列を用いて空間を最適化することができ,スクロール配列は動的計画基礎回顧で何度も言及されている.
接尾辞配列法では、接尾辞配列を結合して初期化する時間的複雑度はO(m+n)であり、接尾辞配列の文字列を並べ替えると、接尾辞配列にm+n個の接尾辞サブ列があり、サブ列間比較があるため、複雑度はO((((m+n)*l*lg(m+n))であり、最長子列が接尾辞配列を遍歴し、複雑度はO(m+n)であるため、総時間的複雑度はO((m+n)*l*lg(m+n))であり、空間的複雑度はO(m＋n)であった.
総じて接尾辞配列を用いてデータに対していくつかの“前処理”をして、効率の上でやはり少なからず向上することができます.
このセクションの関連コードはここでダウンロードできます.