1、先科普下最长公共子序列 & 最长公共子串的区别：

找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。

2、最长公共子串

 

 

其实这是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧："bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")

　　 b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　1

a　　0　　1　　0

我们看矩阵的斜对角线最长的那个就能找出最长公共子串。

不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。

　　 b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　2

a　　0　　2　　0

这样矩阵中的最大元素就是 最长公共子串的长度。

在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。

2.1 代码如下：

public 

class 

LCString2 {

 

    

public 

static 

void 

getLCString(

char

[] str1, 

char

[] str2) {

        

int 

i, j;

        

int 

len1, len2;

        

len1 = str1.length;

        

len2 = str2.length;

        

int 

maxLen = len1 > len2 ? len1 : len2;

        

int

[] max = 

new 

int

[maxLen];

        

int

[] maxIndex = 

new 

int

[maxLen];

        

int

[] c = 

new 

int

[maxLen]; 

// 记录对角线上的相等值的个数

 

        

for 

(i = 

0

; i < len2; i++) {

            

for 

(j = len1 - 

1

; j >= 

0

; j--) {

                

if 

(str2[i] == str1[j]) {

                    

if 

((i == 

0

) || (j == 

0

))

                        

c[j] = 

1

;

                    

else

                        

c[j] = c[j - 

1

] + 

1

;

                

} 

else 

{

                    

c[j] = 

0

;

                

}

 

                

if 

(c[j] > max[

0

]) { 

// 如果是大于那暂时只有一个是最长的,而且要把后面的清0;

                    

max[

0

] = c[j]; 

// 记录对角线元素的最大值，之后在遍历时用作提取子串的长度

                    

maxIndex[

0

] = j; 

// 记录对角线元素最大值的位置

 

                    

for 

(

int 

k = 

1

; k < maxLen; k++) {

                        

max[k] = 

0

;

                        

maxIndex[k] = 

0

;

                    

}

                

} 

else 

if 

(c[j] == max[

0

]) { 

// 有多个是相同长度的子串

                    

for 

(

int 

k = 

1

; k < maxLen; k++) {

                        

if 

(max[k] == 

0

) {

                            

max[k] = c[j];

                            

maxIndex[k] = j;

                            

break

; 

// 在后面加一个就要退出循环了

                        

}

 

                    

}

                

}

            

}

        

}

 

        

for 

(j = 

0

; j < maxLen; j++) {

            

if 

(max[j] > 

0

) {

                

System.out.println(

"第" 

+ (j + 

1

) + 

"个公共子串:"

);

                

for 

(i = maxIndex[j] - max[j] + 

1

; i <= maxIndex[j]; i++)

                    

System.out.print(str1[i]);

                

System.out.println(

" "

);

            

}

        

}

    

}

 

    

public 

static 

void 

main(String[] args) {

 

        

String str1 = 

new 

String(

"123456abcd567"

);

        

String str2 = 

new 

String(

"234dddabc45678"

);

        

// String str1 = new String("aab12345678cde");

        

// String str2 = new String("ab1234yb1234567");

        

getLCString(str1.toCharArray(), str2.toCharArray());

    

}

}

ref：

LCS的---考虑可能有多个相同的最长公共子串

 

最大子序列、最长递增子序列、最长公共子串、最长公共子序列、字符串编辑距离

2.2 其实 awk 写起来也很容易：

echo 

"123456abcd567

234dddabc45678

"|awk -vFS="

" 'NR==1{str=$0}NR==2{N=NF;for(n=0;n++<N;){s="

";for(t=n;t<=N;t++){s=s"

"$t;

if

(index(str,s)){a[n]=t-n;b[n]=s;

if

(m<=a[n])m=a[n]}

else

{t=N}}}}END{

for

(n=0;n++<N;)

if

(a[n]==m)print b[n]}'

 

ref：

2.3 perl的。。。真心没看懂。。。

 

#!/usr/bin/perl

use 

strict;

use 

warnings;

 

my 

$str1 

=

"123456abcd567"

;

my 

$str2 

= 

"234dddabc45678"

;

my 

$str 

= 

$str1 

. 

"\n" 

. 

$str2

;

 

my 

(

@substr

,

@result

);

$str 

=~ /(.+)(?=.*\n.*\1)(

*PRUNE

)(?{

push 

@substr

,$1})(

*F

)/;

@substr 

= 

sort 

{ 

length

(

$b

) <=> 

length

(

$a

) } 

@substr

;

@result 

= 

grep 

{ 

length 

== 

length 

$substr

[0] } 

@substr

;

print 

"@result\n"

;

ref： 

 

3、最长公共子序列

import 

java.util.Random;

 

public 

class 

LCS {

 

    

public 

static 

void 

main(String[] args) {

 

        

// 随机生成字符串

        

// String x = GetRandomStrings(substringLength1);

        

// String y = GetRandomStrings(substringLength2);

        

String x = 

"a1b2c3"

;

        

String y = 

"1a1wbz2c123a1b2c123"

;

        

// 设置字符串长度

        

int 

substringLength1 = x.length();

        

int 

substringLength2 = y.length(); 

// 具体大小可自行设置

 

        

// 构造二维数组记录子问题x[i]和y[i]的LCS的长度

        

int

[][] opt = 

new 

int

[substringLength1 + 

1

][substringLength2 + 

1

];

 

        

// 从后向前，动态规划计算所有子问题。也可从前到后。

        

for 

(

int 

i = substringLength1 - 

1

; i >= 

0

; i--) {

            

for 

(

int 

j = substringLength2 - 

1

; j >= 

0

; j--) {

                

if 

(x.charAt(i) == y.charAt(j))

                    

opt[i][j] = opt[i + 

1

][j + 

1

] + 

1

;

// 状态转移方程

                

else

                    

opt[i][j] = Math.max(opt[i + 

1

][j], opt[i][j + 

1

]);

// 状态转移方程

            

}

        

}

        

System.out.println(

"substring1:" 

+ x);

        

System.out.println(

"substring2:" 

+ y);

        

System.out.print(

"LCS:"

);

 

        

int 

i = 

0

, j = 

0

;

        

while 

(i < substringLength1 && j < substringLength2) {

            

if 

(x.charAt(i) == y.charAt(j)) {

                

System.out.print(x.charAt(i));

                

i++;

                

j++;

            

} 

else 

if 

(opt[i + 

1

][j] >= opt[i][j + 

1

])

                

i++;

            

else

                

j++;

        

}

    

}

 

    

// 取得定长随机字符串

    

public 

static 

String GetRandomStrings(

int 

length) {

        

StringBuffer buffer = 

new 

StringBuffer(

"abcdefghijklmnopqrstuvwxyz"

);

        

StringBuffer sb = 

new 

StringBuffer();

        

Random r = 

new 

Random();

        

int 

range = buffer.length();

        

for 

(

int 

i = 

0

; i < length; i++) {

            

sb.append(buffer.charAt(r.nextInt(range)));

        

}

        

return 

sb.toString();

    

}

}

 REF：

字符串最大公共子序列以及最大公共子串问题

动态规划算法解最长公共子序列LCS问题

 

 

　　在做OJ题目的时候，经常会用到字符串的处理。例如，比较二个字符串相似度。这篇文章介绍一下求两个字符串的最长公共子序列。

　　一个字符串的子序列，是指从该字符串中去掉任意多个字符后剩下的字符在不改变顺序的情况下组成的新字符串。

　　最长公共子序列，是指多个字符串可具有的长度最大的公共的子序列。

　　(1)递归方法求最长公共子序列的长度

　　　　1)设有字符串a[0...n]，b[0...m]，下面就是递推公式。

             当数组a和b对应位置字符相同时，则直接求解下一个位置；当不同时取两种情况中的较大数值。

　　　　

　　　　2)代码如下：

#include
       
        #include
        
         char a[30],b[30];int lena,lenb;int LCS(int,int);　　///两个参数分别表示数组a的下标和数组b的下标int main(){    strcpy(a,"ABCBDAB");    strcpy(b,"BDCABA");    lena=strlen(a);    lenb=strlen(b);    printf("%d\n",LCS(0,0));    return 0;}int LCS(int i,int j){    if(i>=lena || j>=lenb)        return 0;    if(a[i]==b[j])        return 1+LCS(i+1,j+1);    else        return LCS(i+1,j)>LCS(i,j+1)? LCS(i+1,j):LCS(i,j+1);}
        
       

 　　　　用递归的方法优点是编程简单，容易理解。缺点是效率不高，有大量的重复执行递归调用，而且只能求出最大公共子序列的长度，求不出具体的最大公共子序列。

　　(2)动态规划求最长公共子序列的长度

　　　　动态规划采用二维数组来标识中间计算结果，避免重复的计算来提高效率。

　　　　1)最长公共子序列的长度的动态规划方程

　　　　设有字符串a[0...n]，b[0...m]，下面就是递推公式。字符串a对应的是二维数组num的行，字符串b对应的是二维数组num的列。

　　　　

　　　　另外，采用二维数组flag来记录下标i和j的走向。数字"1"表示，斜向下；数字"2"表示，水平向右；数字"3"表示，竖直向下。这样便于以后的求解最长公共子序列。

　　　　(2)求解公共子序列代码

#include
       
        #include
        
         char a[500],b[500];char num[501][501]; ///记录中间结果的数组char flag[501][501];    ///标记数组，用于标识下标的走向，构造出公共子序列void LCS(); ///动态规划求解void getLCS();    ///采用倒推方式求最长公共子序列int main(){    int i;    strcpy(a,"ABCBDAB");    strcpy(b,"BDCABA");    memset(num,0,sizeof(num));    memset(flag,0,sizeof(flag));    LCS();    printf("%d\n",num[strlen(a)][strlen(b)]);    getLCS();    return 0;}void LCS(){    int i,j;    for(i=1;i<=strlen(a);i++)    {        for(j=1;j<=strlen(b);j++)        {            if(a[i-1]==b[j-1])   ///注意这里的下标是i-1与j-1            {                num[i][j]=num[i-1][j-1]+1;                flag[i][j]=1;  ///斜向下标记            }            else if(num[i][j-1]>num[i-1][j])            {                num[i][j]=num[i][j-1];                flag[i][j]=2;  ///向右标记            }            else            {                num[i][j]=num[i-1][j];                flag[i][j]=3;  ///向下标记            }        }    }}void getLCS(){    char res[500];    int i=strlen(a);    int j=strlen(b);    int k=0;    ///用于保存结果的数组标志位    while(i>0 && j>0)    {        if(flag[i][j]==1)   ///如果是斜向下标记        {            res[k]=a[i-1];            k++;            i--;            j--;        }        else if(flag[i][j]==2)  ///如果是斜向右标记            j--;        else if(flag[i][j]==3)  ///如果是斜向下标记            i--;    }    for(i=k-1;i>=0;i--)        printf("%c",res[i]);}
        
       

　　　　(3)图示

 

1.概念

　　编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括：(1)将一个字符替换成另一个字符，(2)插入一个字符，(3)删除一个字符。

　　相似度，等于“编辑距离+1”的倒数。

2.分析

　　设有字符串a[0...n]，b[0...m]。

　　(1)当a[i]=b[j]时，说明这时候不需要编辑操作。编辑距离保持，即f(i,j)=f(i-1,j-1)

　　(2)当a[i]!=b[j]时，可以有三种编辑操作。

　　其中删除和插入操作，只对一个下标i或者j产生影响。如在下图中，当前匹配到(t1,t2)处，如果采用删除'g'，只改变t1的下标。

　　

 　　其中替换操作，会对2个下标都产生影响。如在下图中，当前匹配到(t1,t2)处，如果将'g'替换成'm'，则下次就需要执行(t1+1,t2+1)处。

      

 　　所以可以推导出下面就是递推公式。

　　

3.用递归求解代码

#include
       
        #include
        
         char *a="abcgh";char *b="aecdgh";int min(int t1,int t2,int t3)   ///求三个数的最小值{    int min;    min=t1
         
          enda)  ///i指示超过a[]的范围时    {        if(j>endb)            return 0;        else            return endb-j+1;    }    if(j>endb)  ///j指示超过b[]的范围时    {        if(i>enda)            return 0;        else            return enda-i+1;    }    if(*(a+i) == *(b+j))    ///如果两个相等，则直接求下一个位置        return calculate(i+1,enda,j+1,endb);    else    {        t1=calculate(i+1,enda,j,endb);  ///删除a[i]或在b中插入a[i]        t2=calculate(i,enda,j+1,endb);  ///删除b[j]或在a中插入b[j]        t3=calculate(i+1,enda,j+1,endb);    ///替换        return 1+min(t1,t2,t3);    }}int main(){    int dis=calculate(0,strlen(a)-1,0,strlen(b)-1);    printf("dis=%d",dis);    return 1;}
         
        
       

 4.用动态规划求解代码

 

#include
       
        #include
        
         #define MAX 1000int dp[MAX][MAX];   ///dp[i][j]表示当前a[0..i-1]与b[0..j-1]的编辑距离char *a="agbgd";char *b="ggd";int min(int t1,int t2,int t3)   ///求三个数的最小值{    int min;    min=t1
        
       

 

来源：http://blog.csdn.net/cangchen/article/details/45045541