`

11077 最长公共子字符串

 
阅读更多

11077 最长公共子字符串(必做)

时间限制:1000MS  内存限制:65535K
提交次数:0 通过次数:0

题型: 编程题   语言: C++;C;VC;JAVA

Description

求两个输入序列的最长的公共子字符串的长度。子字符串中的所有字符在源字符串中必须相邻。

如字符串:21232523311324和字符串312123223445,他们的最长公共子字符串为21232,长度为5。




输入格式

两行,第一行为第一个字符串X,第二行为第二个字符串Y,字符串不含空格并以回车标示结束。X和Y的串长都不超过100000。



输出格式

两行,第一行为最长的公共子字符串的长度,第二行输出一个最长的公共子字符串。

说明:
(1)若最长的公共子字符串有多个,请输出在源字符串X中靠左的那个。
(2)若最长公共子字符串的长度为0,请输出空串(一个回车符)。

如输入:
21232523311324
152341231
由于523和123都是最长的公共子字符串,但123在源串X中更靠左,因此输出:
3
123



输入样例

21232523311324
312123223445



输出样例

5
21232
 

分析:

最长公共子字符串必须是连续的。如果我们使用递归的方法解决的话,对于每一对字符就需要判断前面的是否已构成字串,这就会使子问题出现重复计算的问题。对于重复子问题,还是要使用动态规划的思想。
 
假设需要求的字符串为 str1 , str2 .函数 f(m,n) 求分别以str1[m] , str2[n] 结尾的公共字符串长度。
这有一下递推公式:
 
f(m,n)=0        str1[m] != str2[n] ;
f(m,n)=f(m-1,n-1) + 1      str[m]==str2[n];
 
别忘了递推的特殊边界:
f(0,n)=0;
f(m,0)=0;

 

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

char a[1000],b[1000]; //1000够了

int m[1000][1000];

int aa,bb;

int res=-1;

int mark;

void findL(){

    for(int i=0;i<aa;i++){

        for(int j=0;j<bb;j++){

            if(a[i]==b[j]){

                if(i==0||j==0) m[i][j]=1;

                else{

                    m[i][j] = m[i-1][j-1]+1;

                }

            }else{

            m[i][j]=0;

            }

        }

    }

    for(int i=aa-1;i>=0;i--){   //输出在源字符串X中靠左的那个

        for(int j=0;j<bb;j++){

            if(res<=m[i][j])    // 注意是小于等于

               {

                   res = m[i][j];

                   mark = i;

               }

        }

    }

}

int main()

{

    freopen("in.txt","r",stdin);

    cin >> a >> b;

    aa=strlen(a);bb=strlen(b);

    //cout << m<< n;

    findL();

    cout << res<< endl;

    for(int i=mark-res+1;i<mark+1;i++){

       cout << a[i];

    }

    return 0;

}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics