我的 "Longest Common substring with at most k mismatches" 复杂度为 O(m*n) space 的算法给出了大字符串输入的错误答案

Question

我是这个平台的新手，所以请多多包涵。我的程序基于最长子串问题，使用动态编程没有不匹配。这是 D-P 解决方案的 link。

https://www.geeksforgeeks.org/longest-common-substring-dp-29/.

这是对原问题的link。

https://www.hackerrank.com/challenges/substring-diff/problem

我基本上使用 d-p 解决方案中的 table 来存储两个子字符串中的不匹配数，而不是像在原始问题中那样使用它来计算匹配数。对于 table 中小于或等于的所有值，我存储了最大可能长度并打印出来。

虽然我的解决方案适用于小型测试用例，但在较大的测试用例中给出了错误的答案。

这是我的 C++ 代码。

int substringDiff(int k, string s1, string s2) {
vector <vector<int>> v(s1.size()+1,vector<int>(s2.size()+1,0));
int len=0;
for(int i=1;i<=s1.size();i++) 
{
for(int j=1;j<=s2.size();j++)
{
    if(s1[i-1]==s2[j-1])
        v[i][j]=v[i-1][j-1];
    else
        v[i][j]=v[i-1][j-1]+1;
    if(v[i][j]<=k)
        len=max(len,min(i,j));
 }
}

return len;
}

我在网上搜索并找到了一些更好的解决方案，但我不明白为什么我的代码不起作用。请帮忙

Answer 1

当两个最长公共子串都不是每个输入字符串的前缀时，您的程序不会给出正确答案。

例如，substringDiff(0, "xa", "ya") returns 0 而 1 是预期的。

这是因为只计算与任一字符串开头的差异数。

示例 table substringDiff(0, "xa", "ya"):

  y a
x 1 1
a 1 1

为了获得正确答案，使用这个table，

设置一个长度，检查是否存在满足该长度的公共子串
使用长度检查：可以通过brute-force使用table来完成（v[i][j] - v[i-length][j-length]是以i-th字符结尾的子字符串不匹配的数量s1 和 j-th 字符 s2)
使用此检查，对存在满足公共子字符串的最大长度进行二进制搜索。

我的 "Longest Common substring with at most k mismatches" 复杂度为 O(m*n) space 的算法给出了大字符串输入的错误答案

My "Longest Common substring with at most k mismatches" algorithm with O(m*n) space complexity is giving wrong answers with large string inputs

c++

algorithm

dynamic-programming

longest-substring