LCS 最长公共子序列-蒲公英云

LCS 最长公共子序列

首先要明白什么是子序列，什么是子串；

设：主串长度为n；

子序列：从主串中抽出少于n的元素组成的序列（这些抽出的元素比一定是连续的他们的相对位置不变）；

    例：主串为abdexk
           那么在子序列中若有a，则a必须在所有其他元素的前面，若有b，除了a，b排在最前面............（相对位置不变）

子串：从主串中抽出少于n的元素组成的序列（这写被抽出来的元素必须是连续的，相对位置不变）；

   例：主串为afoijnc
          那么在子串中，若有a和i，则子串中必有一段时afoi，不会出现afi、aoi或ai的的情况。

最长公共子序列的求法网上有很多，这里不多做解释，直接上模板了。

（目前为止只知道这一个）

#define maxx(a,b) (a>b?a:b)
char s1[1200],s2[1200];
int p[1200][1200];
void LCS(){
    int len1=strlen(s1);
    int len2=strlen(s2);
    int i,j;
    for(i=1;i<=len1;i++){
        for(j=1;j<=len2;j++){
            if(s1[i-1]==s2[j-1])
                p[i][j]=p[i-1][j-1]+1;
            else
                p[i][j]=maxx(p[i-1][j],p[i][j-1]);
        }
    }
}

以上这种会超内存，下面给出优化版

#define maxx(a,b) (a>b?a:b)
char s1[1200],s2[1200];
int p[2][1200];                                            
void LCS(){
    int len1=strlen(s1);
    int len2=strlen(s2);
    int i,j;
    for(i=1;i<=len1;i++){
        for(j=1;j<=len2;j++){
                int x=i%2;                    //滚动数组
                int y=1-x;
            if(s1[i-1]==s2[j-1])
                p[x][j]=p[y][j-1]+1;
            else
                p[x][j]=maxx(p[y][j],p[x][j-1]);
        }
    }
}