string - O(m*n) 的最长公共(public)子串非 DP 解决方案

Question

问题的定义是:

Given two strings, find the longest common substring.

Return the length of it.

我正在解决这个问题，我想我用 O(m*n) 的时间复杂度解决了它。但是我不知道为什么当我查找解决方案时，都在谈论最佳解决方案是动态规划 - http://www.geeksforgeeks.org/longest-common-substring/

这是我的解决方案，您可以在这里进行测试:http://www.lintcode.com/en/problem/longest-common-substring/

int longestCommonSubstring(string &A, string &B) {

    int ans = 0;
    for (int i=0; i<A.length(); i++) {
        int counter = 0;
        int k = i;
        for (int j=0; j<B.length() && k <A.length(); j++) {

            if (A[k]!=B[j]) {
                counter = 0;
                k = i;

            } else {
                k++;
                counter++;
                ans = max(ans, counter);

            }  
        }
    }

    return ans;        
}

我的想法很简单，从字符串A的第一个位置开始，看我能匹配到字符串B的最长子串是什么，然后从字符串A的第二个位置开始，看我能匹配到的最长子串是什么…… .

我的解决方案有问题吗？还是不是 O(m*n) 的复杂度？

Answer 1

好消息:您的算法是 O(mn)。坏消息:它无法正常工作。

你的内部循环是错误的:它的目的是在 B 中找到 A[i:] 的最长初始子串，但它是这样工作的:

j = 0
While j < len(B)
   Match as much of A[i:] against B[j:]. Call it s.
   Remember s if it's the longest so far found.
   j += len(s)

这无法找到最长的匹配项。例如，当 A = "XXY"和 B = "XXXY"且 i=0 时，它会找到 "XX"作为​​最长匹配而不是完整匹配 "XXY"。

这是显示错误结果的代码的可运行版本(稍微转录成 C):

#include <string.h>
#include <stdio.h>

int lcs(const char* A, const char* B) {
    int al = strlen(A);
    int bl = strlen(B);
    int ans = 0;
    for (int i=0; i<al; i++) {
        int counter = 0;
        int k = i;
        for (int j=0; j<bl && k<al; j++) {
            if (A[k]!=B[j]) {
                counter = 0;
                k = i;
            } else {
                k++;
                counter++;
                if (counter >= ans) ans = counter;
            }  
        }
    }
    return ans;        
}

int main(int argc, char**argv) {
    printf("%d\n", lcs("XXY", "XXXY"));
    return 0;
}

运行这个程序输出“2”。