流离之人追逐幻影

用户名：pwj666

访问量：60209

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

最长公共子串（弱化版）

　　作者: 流离之人追逐幻影　　　　发表时间：2019-10-20 16:50:34 浏览：253　|　评论：0　

PS:串一定是连续的，序列可以是不连续的
时间复杂度O(len1*len2)
------------

问题：求2个字符串的最长公共子串

------------

```
字符串 str1="abcde"，str2="abcde"
```
如果两个串相同，那么矩阵的对角线全都是1。
![](/image_editor_upload/20191020044541_32120.png)
```
串1是abcdefg，串2是acdaefg
```
![](/image_editor_upload/20191020044632_66740.png)
为了在求最长公共子串时，使得判断更加简单，我们把上图改成下图。

![](/image_editor_upload/20191020044723_79632.png)

代码：
```
#include <iostream>

using namespace std;

int main()

{
	string str1, str2;  // 声明两个字符串变量

getline(cin, str1); // 样例中含有空格

getline(cin, str2); // 必须要整行输入才行

int a[255][255];    // 声明一个二维数组存储两个串的映射
	// 获取两个串的字符串长度

int str1Len = str1.length(), str2Len = str2.length();

// maxLen表示最长公共子串的长度

// endIndex表示最长公共子串最后一个字符的下标
	int maxLen = 0, endIndex = 0;

// 使用嵌套循环来遍历两个串
	for (int i = 0; i < str1Len; i++)

for (int j = 0; j < str2Len; j++)

{

if (str1[i] == str2[j]) // 如果两个字符相同

// 如果是在行头或列头，表示开始位置，所以赋值为1

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

// 否则不是开头位置，则赋值为上个对角位置的值+1

else a[i][j] = a[i - 1][j - 1] + 1;

else a[i][j] = 0;       // 否则就是字符不同，赋值为0

if (a[i][j] > maxLen)

{

maxLen = a[i][j];	// 获取最长公共子串的最大长度

// 获取串1的最长公共子串最后一个字符的下标

endIndex = i;

}

// 输出最长公共子串，注意起点和终点

for (int i = endIndex - maxLen + 1; i <= endIndex; i++)

cout << str1[i];

return 0;

}
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

精彩推荐

C语言训练-数字母（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

WU-printf基础练习2 （C++代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

DNA （C语言代码）

Tom数（C语言代码）

杨辉三角（C语言代码）

1048题解（读入回车问题）

蓝桥杯历届试题-翻硬币（C++代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

最长公共子串（弱化版）

评论区

精彩推荐

C语言训练-数字母（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

WU-printf基础练习2 （C++代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

DNA （C语言代码）

Tom数（C语言代码）

杨辉三角（C语言代码）

1048题解（读入回车问题）

蓝桥杯历届试题-翻硬币（C++代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

你的开发任务 （C++代码）写到一半，等有心情回来补全

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

最长公共子串（弱化版）

评论区

精彩推荐

C语言训练-数字母 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

WU-printf基础练习2 （C++代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

DNA （C语言代码）

Tom数 （C语言代码）

杨辉三角 （C语言代码）

1048题解（读入回车问题）

蓝桥杯历届试题-翻硬币 （C++代码）

你的开发任务（C++代码）写到一半，等有心情回来补全

母牛的故事（C语言代码）

　　评论区

C语言训练-数字母（C语言代码）

Tom数（C语言代码）

杨辉三角（C语言代码）

蓝桥杯历届试题-翻硬币（C++代码）