Jan 11

LCS Problem 最长公共子串   不指定

felix021 @ 2007-1-11 14:47 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(6693) | 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 


flymouseEnglishpoor 
comeonflymouseinenglish 


Sample Output 




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 &#124;&#124; 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



欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
tmd
2008-5-2 20:41
就是写的代码太难看了
felix021 回复于 2008-5-2 21:40
转载的, 直接帖, 没有排版 - -||
tmd
2008-5-2 20:39
好东西
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]