最长公共子串

前言

它比最长公共子序列多了一个要求，就是要求子串是连续的，做法跟最长公共子序列的做法大致相同，只是在一处判断的处理改变了。

做法

定义一个二维数组C[i][j],记录str1(0~i)和str2(0~j)的最长公共子串。
定义一个max，记录填表过程中出现的最大值。

动态方程

if str1[i] == str2[j]
c[i][j] = c[i-1][j-1] + 1;
if str1[i] != str2[j]
c[i][j] = 0; //因为i和j位置上面的字符不等，那么到该位置公共子串就不连续，所以此时的最长公共子串的长度为0

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
using namespace std;

int lcs(char a[],char b[],int n,int m){
    if (n==0||m==0) {
        return 0;
    }else{
        int count[n+1][m+1];
        int max = 0;
        memset(count, 0, sizeof(count));
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {
                if (a[i-1]==b[j-1]) {
                    count[i][j] = count[i-1][j-1]+1;
                    if (count[i][j]>max) {
                        max = count[i][j];
                    }
                }else{
                    count[i][j] = 0;
                }
           }
        }
        return max;
    }

}




int main(int argc, const char * argv[]) {
    char a[] = "abccbd";
    char b[] = "bbccbd";
    cout<<lcs(a,b,6,6)<<endl;
    return 0;
}

Comments