LCS Problem 最长公共子串

什么是蓝牙

C语言中随机函数应用

Jan 11

felix021 @ 2007-1-11 14:47 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(8613) | Via 本站原创

大 | 中 | 小

LCS Problem 最长公共子串
武汉大学ACM OJ第1047题
http://acm.whu.edu.cn/noah/problem/problem.jsp?problem_id=1047

LCS Problem

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

Time Limit:1000MS Memory Limit:65536KB
Total Submit:474 Accepted:98

--------------------------------------------------------------------------------
Description

Recently, Flymouse reads a book about Algorithm and Data Structure. The book reads: there are two types of LCS Problems. One is Longest Common
Subsequence problem. By the way of Dynamic Programming, we could solve this problem. The other is Longest Common Substring problem, which is
to find the longest string that is substrings of the two strings. For example, given the following two strings:
1. flymouseEnglishpoor
2. comeonflymouseinenglish
The longest common substring is flymouse, the length of this string is 8.

Input

The first line contains a single integer t (1 <= t <= 100), the number of test cases.There will be two lines for each test case,each line contains
a string (The length of the two strings are no more than 1000 and you can assure all strings will not contains any punctuation or other separators).

Output

For each test case, you should output one line containing the longest common substring’s length of the two strings of the test case.

Sample Input

1
flymouseEnglishpoor
comeonflymouseinenglish

Sample Output

8

Hint

flymouse

Source

The 4th Wuhan University Programming Contest(Personal Selected Round)

C++
LCS算法:

通常两个字符串的最大公共子串的问题是通过下面的算法来完成的：把字符串1（长度m）横排，串2（长度n）竖排，得到一个m×n的矩阵c，矩阵的每个元素的值如下，如果m[i]=n[j]，则c[j][i]=1,否则，c[j][i]=0。然后找出矩阵中连续是1的对角线最长的一个，则对角线的长度就是公共子串的长度.

下面是字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。不难找到，红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为：21232

0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。下面是新的矩阵生成方式：

　　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
　　1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
　　0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
　　1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
　　1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
　　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
　　0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

　　不用多说，你大概已经看出来了。当字符匹配的时候，我们并不是简单的给相应元素赋上1，而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。

　　这样做速度比较快，但是花的空间太多。我们注意到在改进的矩阵生成方式当中，每生成一行，前面的那一行就已经没有用了。因此我们只需使用一维数组即可.

LCS算法的C++实现：

#include<iostream>
using namespace std;

char* LCS(char* left,char* right);

int main(){
char *left,*right;
left = new char[1024];
right = new char[1024];
cout << "please input the first string:";
cin >> left;
cout << "please input the second string:";
cin >> right;
cout << "最长公共子串是：";
cout << LCS(left,right)<<endl;
return 0;
}

char* LCS(char*left,char* right){
int lenLeft,lenRight;
lenLeft = strlen(left);
lenRight = strlen(right);
int *c = new int[lenRight];
int start,end,len;
end = len = 0;
for(int i = 0; i < lenLeft; i++){
for(int j = lenRight-1; j >= 0; j--){
if(left[i] == right[j]){
if(i == 0 || j == 0)
c[j] = 1;
else
c[j] = c[j-1]+1;
}
else
c[j] = 0;
if(c[j] > len){
len = c[j];
end = j;
}
}
}
char *p = new char[len+1];
start = end - len + 1;
for(i = start; i <= end; i++)
p[i - start] = right[i];
p[len] = '\0';
return p;
}

Visual Basic

LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置。

下面是字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。不难找到，红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为：21232

0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。下面是新的矩阵生成方式：

0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

不用多说，你大概已经看出来了。当字符匹配的时候，我们并不是简单的给相应元素赋上1，而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。

这样做速度比较快，但是花的空间太多。我们注意到在改进的矩阵生成方式当中，每生成一行，前面的那一行就已经没有用了。因此我们只需使用一维数组即可。最终的代码如下：

Private Function LCS(ByVal str_1 As String, ByVal str_2 As String) As String
If str_1 = "" Or str_2 = "" Then Return ""

Dim c(str_1.Length) As Integer
Dim max, maxj, i, j As Integer
maxj = 0 : max = 0 '这两个是标志变量

For i = 0 To str_2.Length - 1
For j = str_1.Length - 1 To 0 Step -1
If str_2.Chars(i) = str_1.Chars(j) Then
If i = 0 Or j = 0 Then
c(j) = 1
Else
c(j) = c(j - 1) + 1
End If
Else
c(j) = 0
End If

If c(j) > max Then '把>改成>=则返回最后一个最长匹配子串
max = c(j) : maxj = j '更新标志变量
End If
Next
Next

If max = 0 Then Return ""
Return str_1.Substring(maxj - max + 1, max) '直接从标志变量得出结果

End Function

参考资料：http://dev.csdn.net/develop/article/52/52658.shtml

欢迎扫码关注：