一、题目描述
描述：
计算两个字符串的最大公共子串（Longest Common Substring）的长度，字符区分大小写。
输入：
输出：
输出一个整数
样例输入：1
asdfas werasdfaswer
样例输出：1
6
二、解题报告
与最长公共子序列（参见《动态规划DP》）一样，最长公共子串也可以使用动态规划解决，只不过思路不太一样。准确地说，是打表的方式不一样。
举个例子：s1 = bab，s2 = caba。表如下
具体打表的方法是：
- 第一行、第一列初始化为 0；
- 对于其他的格子：
- 若对应的两个字符相等，格子的值设为左上角的值加 1。
- 若对应的两个字符不相等，直接置 0 。
这样的话，表中的最大元素就是 最长公共子串 的长度。并且也可以很容易看出最长公共子串有 2 个，分别是ba和ab。
C++代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
int getLCStringLength(string s1, string s2)
{
if(s1 == "" || s2 == "")
return 0;
int m = s1.size();
int n = s2.size();
vector<vector<int> > table(m+1, vector<int>(n+1));
int biggest = 0; // 记录表中最大值
for(int i=0; i<m+1; ++i)
{
for(int j=0; j<n+1; ++j)
{
// 第一行和第一列置0
if (i == 0 || j == 0)
table[i][j] = 0;
else if(s1[i-1] == s2[j-1])
{
table[i][j] = table[i-1][j-1] + 1;
if(table[i][j] > biggest)
biggest = table[i][j];
}
else // 不相等置0
table[i][j] = 0;
}
}
return biggest;
}
int main ()
{
string input, s1, s2;
getline(cin, input);
stringstream ss(input);
ss >> s1;
ss >> s2;
cout << getLCStringLength(s1, s2) << endl;
return 0;
}
三、扩展
如何输出所有的最长公共子串？
很简单，我们记录下 s1 和 s2 的公共子串分别在 s1 、s2 中起始位置（即表中值为 1 的坐标）。打表完成以后，我们已经知道了最长公共子串的长度length，通过substr()判断即可：1
s1.substr(i-1, length) == s2.substr(j-1, length)
C++代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#include <iostream>
#include <string>
#include <vector>
using namespace std;
void printLCString(string s1, string s2)
{
if(s1 == "" || s2 == "")
return;
int m = s1.size();
int n = s2.size();
vector<vector<int> > table(m+1, vector<int>(n+1));
int biggest = 0; // 记录表中最大值
vector<pair<int, int> > firstPos; // 记录子串开始的坐标
for(int i=0; i<m+1; ++i)
{
for(int j=0; j<n+1; ++j)
{
// 第一行和第一列置0
if (i == 0 || j == 0)
table[i][j] = 0;
else if(s1[i-1] == s2[j-1])
{
table[i][j] = table[i-1][j-1] + 1;
if(table[i][j] > biggest)
biggest = table[i][j];
if(table[i][j] == 1)
firstPos.push_back(make_pair(i, j));
}
else // 不相等置0
table[i][j] = 0;
}
}
// 输出所有的最长公共子串
vector<pair<int, int> >::iterator beg = firstPos.begin();
for( ; beg!=firstPos.end(); ++beg)
{
int start1 = beg->first-1;
int start2 = beg->second-1;
if(s1.substr(start1, biggest) == s2.substr(start2, biggest))
cout << s1.substr(start1, biggest) << endl;
}
}
int main ()
{
string s1 = "hello,world,james";
string s2 = "james is saying hello";
printLCString(s1, s2);
return 0;
}