最长的公共子字符串非 DP 解，带 O(m*n)

Question

问题的定义是：

给定两个字符串，找到最长的公共子字符串。

返回它的长度。

我

正在解决这个问题，我想我用 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("%dn", lcs("XXY", "XXXY"));
    return 0;
}

运行此程序输出"2"。

Answer 2

你的解决方案是O（nm）复杂度，如果你将结构与提供的算法进行比较，它是完全相同的;但是，你的不记住。

链接中提供的动态算法的一个优点是，在相同的复杂度类时间内，它可以调用 O（1） 中的不同子字符串长度;否则，它对我来说看起来不错。

这是一种不时发生的事情，因为存储子空间解决方案并不总是会导致更好的运行时（在第一次调用时）并导致相同的复杂度类运行时（例如，尝试使用动态解决方案计算第 n 个斐波那契数并将其与尾递归解决方案进行比较。请注意，在这种情况下，就像您的情况一样，在数组第一次填充后，每次连续调用返回一个答案会更快。