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

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

**描述：**

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

**输入：**

输入两个字符串

**输出：**

输出一个整数

**样例输入：**

asdfas werasdfaswer

**样例输出：**

6

参考网址：[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

发表评论取消回复

表情：

评论列表（有 0 条评论，220人围观）

还没有评论，来说两句吧...

相关阅读

相关面试（动态规划算法之：最长公共子序列 & 最长公共子串（LCS））

收藏 1、先科普下最长公共子序列 & 最长公共子串的区别：找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。 2、最长公共

迷南。/ 2023年10月17日 14:00/ 0 赞/ 44 阅读

相关最长公共字串（动态规划）

【题目】给定两个字符串 str1 和 str2，返回两个字符串的最长公共子串。【举例】 str1 =“1AD12345CD ”， str2 =“12345E

落日映苍穹つ/ 2022年08月18日 02:19/ 0 赞/ 174 阅读

相关【动态规划】求最长公共子串，最长回文子串

题目 : 给定两个字符串，求出它们之间连续的最长的相同子字符串的长度。 eg : fbaabe，ebaabf，连续最长子串长度为4。注意：求最长回文子串也可以用求最长公

朴灿烈づ我的快乐病毒、/ 2022年08月09日 00:59/ 0 赞/ 258 阅读

相关动态规划：求最长公共子串/最长公共子序列

最长公共子序列和最长公共子串区别最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence

我不是女神ヾ/ 2022年08月08日 03:24/ 0 赞/ 261 阅读

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

描述：计算两个字符串的最大公共子串（Longest Common Substring）的长度，字符不区分大小写。输入：输入两个字符串输出：输出一个整数样

迷南。/ 2022年06月08日 10:07/ 0 赞/ 221 阅读

相关动态规划-最长公共子序列

一，问题描述给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB 则这

痛定思痛。/ 2022年05月11日 11:50/ 0 赞/ 288 阅读

相关动态规划---求最长公共子序列和最长公共子串（C语言）

参考：[https://blog.csdn.net/someone\_and\_anyone/article/details/81044153][https_blog.csdn

阳光穿透心脏的1/2处/ 2022年02月20日 07:08/ 0 赞/ 265 阅读

相关动态规划问题 —— 最长公共子串

题目描述链接：[https://www.nowcoder.com/questionTerminal/02e7cc263f8a49e8b1e1dc9c116f7602][

系统管理员/ 2022年02月17日 01:41/ 0 赞/ 248 阅读

相关动态规划最长公共子串

核心思路和最长公共子序列一样区别在于子串必须连续可以先看我之前这篇文章 [最长公共子序列问题总结][Link 1] 最长公共子串同样是构造二维数组存储最大值，只不过去

我就是我/ 2021年08月11日 20:24/ 0 赞/ 409 阅读

相关【动态规划】最长公共子序列与最长公共子串

[来源][Link 1] 1. 问题描述子串应该比较好理解，至于什么是子序列，这里给出一个例子：有两个母串 cnblogs belong 比如序列

「爱情、让人受尽委屈。」/ 2021年06月24日 16:12/ 0 赞/ 526 阅读