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

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

**描述：**

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

**输入：**

输入两个字符串

**输出：**

输出一个整数

**样例输入：**

asdfas werasdfaswer

**样例输出：**

参考网址：[http://blog.csdn.net/u013074465/article/details/45392687][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;
    }

[http_blog.csdn.net_u013074465_article_details_45392687]: http://blog.csdn.net/u013074465/article/details/45392687