最小公共子串.txt

//法一：m*n的表
#include<iostream>
#include<string>
using namespace std;

int lcs(string str1,string str2,int len1,int len2)
{
    int dp[len1+1][len2+1];
    int max1 = 0;
    for(int i=0;i<=len1;++i)dp[i][0]=0;
    for(int j=0;j<=len2;++j)dp[0][j]=0;
    for(int i=1;i<=len1;++i)
    {
        for(int j=1;j<=len2;++j)
        {
           if(str1[i-1]==str2[j-1])
           {
               dp[i][j]=max(dp[i-1][j-1]+1,dp[i-1][j]);
               max1 = max(dp[i][j],max1);
               cout<<dp[i][j];
           }
           else
               {
               dp[i][j]=0;
               max1 = max(dp[i][j],max1);
               cout<<dp[i][j];
           }
        }
        cout<<endl;
    }
    return max1;
}
int main()
{
     string str1;
     string str2;
     while(getline(cin,str1))
     {
         getline(cin,str2);
         int len1 = str1.size();
         int len2 = str2.size();
         cout<<lcs(str1,str2,len1,len2)<<endl;
     }
     return 0;
 }
//法二移动比较法len1+len2
#include<iostream>
#include<string>
using namespace std;

int lcs(string str1,string str2,int len1,int len2)
{
    int i,len,s1_start,s2_start,idx,curmax,max;
    len = len1 + len2;
    max = 0;
    for(i = 0 ; i < len ; i++)
    {
        s1_start = s2_start = 0;
        if(i < len1)
            s1_start = len1 - i;    //每次开始匹配的起始位置
        else
            s2_start = i - len1;
        curmax = 0;
        for(idx = 0 ; ( s1_start + idx < len1 ) && ( s2_start + idx < len2 ); idx++ )
        {
            if(str1[s1_start+idx]==str2[s2_start+idx])
                curmax++;
            else     //只要有一个不相等，就说明相等的公共字符断了，不连续了，要保存curmax与max中的最大值，并将curmax重置为0
            {
                max = curmax > max ? curmax : max;
                curmax = 0;
            }
        }
        max = curmax > max ? curmax : max;
    }
    return max;
}
int main()
{
     string str1;
     string str2;
     while(getline(cin,str1))
     {
         getline(cin,str2);
         int len1 = str1.size();
         int len2 = str2.size();
         cout<<lcs(str1,str2,len1,len2)<<endl;
     }
     return 0;
 }