最长公共子串（动态规划）-蒲公英云

最长公共子串（动态规划）

迷南。 2022-06-08 10:07 368阅读 0赞

描述：

计算两个字符串的最大公共子串（Longest Common Substring）的长度，字符不区分大小写。

输入：

输入两个字符串

输出：

输出一个整数

样例输入：

asdfas werasdfaswer

样例输出：

参考网址：http://blog.csdn.net/u013074465/article/details/45392687

这里的最大公共字串要求的字串是连续的。

求字串的方法和求子序列方法类似：

当s[i] == t[j]时，子序列长度f[i][j] = f[i - 1][j - 1] + 1；只是当str1[i] ！= str2[j]时，f[i][j]长度要为0，而不是max{f[i - 1][j], f[i][j - 1]}。

#include<iostream>
#include<string>
#include<cstring>
#define MAXN 200
using namespace std;
int f[MAXN+10][MAXN+10];
string s,t;
int main()
{
    memset(f,0,sizeof(f));
    int i,j,ls,lt;
    cin>>s>>t;
    ls=s.size();
    lt=t.size();
    int maxn=0;
    for(i=0;i<ls;i++)//将大写转化为小写 
    {
        if(s[i]>='A'&&s[i]<='Z') s[i]=tolower(s[i]);
    }
       for(i=0;i<lt;i++)
       {
            if(t[i]>='A'&&t[i]<='Z') t[i]=tolower(t[i]);
       }
    for(i=1;i<=ls;i++)
    {
        for(j=1;j<=lt;j++)
        {
            if(s[i-1]==t[j-1])
            {
                f[i][j]=f[i-1][j-1]+1;
                if(maxn<f[i][j]) maxn=f[i][j];
            }
            else
            {
                f[i][j]=0;
            }
        }
    }
    cout<<maxn<<endl;
    return 0;
}