至多K个不匹配子字符串？

Question

我尝试使用暴力方法解决这个问题，但是以下优化算法对某些测试用例给出了错误的结果。我已经尝试过，但无法找到代码中的问题，有人能帮我吗。

问题：给定一个字符串S和整数K，找到整数C，它等于拥有相同长度且Mismatch（S1，S2）≤K的子字符串对(S1，S2)的数量，其中mismatch函数定义如下。

mismatch函数

mismatch(s1，s2)是S1和S2中字符不同的位置数。例如，mismatch(bag，boy)=2(第二个和第三个位置存在不匹配)，mismatch(cat，cow)=2(同样，在第二个和第三个位置存在不匹配)，Mismatch(London，Mumbai)=6(因为两个字符串在每个位置上的字符都不同)。London的第一个字符是'L'，而Mumbai的第一个字符是'M'，London的第二个字符是'o'，而Mumbai的第二个字符是'u'，以此类推。

int main() {

int k;
char str[6000];
cin>>k;
cin>>str;
int len=strlen(str);
int i,j,x,l,m,mismatch,count,r;

count=0;

 for(i=0;i<len-1;i++)
   for(j=i+1;j<len;j++)
   {  mismatch=0;
     for(r=0;r<len-j+i;r++)
   {  

       if(str[i+r]!=str[j+r])
         { ++mismatch;
           if(mismatch>=k)break;
         }
    if(mismatch<=k)++count;
   } 
  }
cout<<count;
return 0;
}

示例测试用例

1. Test case (passing for above code)

   **input** 
   0
   abab
   
   **output** 
   3
   

2. Test case (failing for above code)

   **input** 
   3
   hjdiaceidjafcchdhjacdjjhadjigfhgchadjjjbhcdgffibeh
   
   **expected output**
   4034
   
   **my output**
   4335 
   

- decoder

---

请学会格式化您的代码，这看起来非常糟糕！清晰的代码是减少错误的一半。 - meaning-matters

这段代码有什么优化过的地方吗？在我看来它像是暴力破解。你能发一下你之前的版本吗？ - vgru

还有没有更快的方法来完成这个任务？ - decoder

在之前的代码中，我再次迭代完整的子字符串，而不仅仅是比较下一个字符。但你是正确的，这只是一个非常小的改进。 - decoder

@Groo：是的，它通过在任何时候都不循环子字符串长度来进行优化。直接实现将测试所有O(n^2)子字符串与相同长度的所有O(n)后续子字符串，使用O(n)的不匹配计数。这是O(n^4)。而这个算法是O(n^3)。 - Mike Housky

Answer 1

您有两个错误。首先，

for(r=1;r<len;r++)

应该是

for(r=1;r<=len-j;r++)

否则，

str[j+r]

在某个时刻，将开始比较空终止符后面的字符（即字符串的末尾）。最大的 r 可以是从第 j 个索引到最后一个字符的剩余字符数。

其次，编写

str[i+r]

并且

str[j+r]

跳过i和j字符的比较，因为r至少为1。您应该编写：

for(r=0;r<len-j;r++)

- Andrew Cheong

---

是的，抱歉实际上应该是for(r=0;r<=len-j+i;r++)，已在上面的代码中进行了更正，但仍然无法工作。感谢快速回复。 - decoder

你的意思应该是 r<len-j+1 而不是 r<len-j+i。但我不同意。以 abab 为例，len 是4，对吧？假设 i 是0，j 是1。那么根据你的代码，r 将会计数到并包括 4-1+1。也就是4。所以当你执行 str[j+r] 时，你得到的是 str[5]，这是越界的。也许你的意思是 r<=len-j-1，这与我写的 r<len-j 是一样的。哦，或者，也许你的意思是 r<=len-(j-1)，这也是正确的。 - Andrew Cheong

不好意思，我的意思是 r<len-j+i，根据您的例子 i=0，j=1，那么 r 将从 r=0 开始计数，直到 r<(4-1+0)=3。所以 r 的取值将为 r=0、r=1、r=2，对吗？因为 str[j+r] 的最大值应该是 str[1+2]=str[3]，对吧？ - decoder

@decoder：如果len=4，i=2和j=3，那么len-j+i是3。这意味着您将在某个时候检查超出字符串范围的str[2+2]==str[3+2]。 - vgru

@Groo明白了，谢谢你，现在得到了正确的答案。但是对于某些输入仍然会出现TLE，有没有更快的方法来解决这个问题？ - decoder

Answer 2

你有两个基本错误。 当mismatches> k时，你退出了，而不是当mismatches>k（mismatches == k是可接受的数字），并且r变得太大。 这些使最终计数朝相反的方向偏斜，但是，正如你看到的，第二个错误“获胜”。

真正的内部循环应该是：

for (r=0; r<len-j; ++r)
{
     if (str[i+r] != str[j+r])
     {
           ++mismatch;
           if (mismatch > k)
                break;
      }
      ++count;
 }

r是子字符串的索引，j+r必须小于len才能作为右子字符串的有效值。由于i<j，如果str[j+r]有效，则str[i+r]也有效，因此无需在上限计算中涉及i。

此外，您希望在不匹配>k时中断，而不是在>=k时中断，因为允许k个不匹配。

接下来，如果在增加不匹配之后测试了太多的不匹配，您就不必在计数之前再次测试它。

最后，r<len-j（而不是<=）的上限意味着尾随的'\0'字符不会作为str[j+r]子字符串的一部分进行比较。当j+r>= len时，您正在比较该字符及更多字符，但是在发生这种情况时，不匹配的数量少于k。

---

注意：您询问了一种更快的方法。有一种方法，但编程更加复杂。使外部循环在起始索引值之间的差值delta上。(0<delta<len)然后，使用类似以下内容计算所有可接受的匹配项的数量：

count = 0; for delta = 1 to len-1 set i=0; j=delta; mismatches=0; r=0; while j < len .. 找到第k个不匹配或字符串结尾: while mismatches < k and j+r

因此，计算这些r个子字符串的数量，并移动到下一个位置i=i+1,j=j+1和新长度r=r-1，如果左侧删除了不相等的字符，则减少不匹配计数。

很容易看出，在每个循环中，r要么增加1，要么j增加1，而(j+r)保持不变。两者都将在O(n)时间内到达len，因此整个过程是O(n^2)。

编辑：我修复了r的处理方式，因此上面的内容应该更加伪正确。 O(n^2)运行时间的改进可能会有所帮助。

重新编辑：修复了注释错误。 再次编辑：算法中有更多的拼写错误和增量错误，大多数是拼写不匹配并且增加了2而不是1。

- Mike Housky

---

“delta”的值是多少？它是否会改变？ - vgru

我顺便提到了那个。这里隐含着一个循环，它的范围是0 < delta < len。所有“有趣”的事情都发生在内部循环中。 - Mike Housky

Answer 3

@Mike，我对你的逻辑进行了一些修改，这是正确的代码...

#include<iostream>
#include<string>
using namespace std;
int main()
{
long long int k,c=0;
string s;
cin>>k>>s;
int len = s.length();
for(int gap = 1 ; gap < len; gap ++)
{
    int i=0,j=gap,mm=0,tmp_len=0; 


        while (mm <=k && (j+tmp_len)<len)
        {
            if (s[i+tmp_len] != s[j+tmp_len])
                mm++;
            tmp_len++;
        }
       // while (((j+tmp_len)<len) && (s[i+tmp_len]==s[j+tmp_len]))
         //   tmp_len++;
        if(mm>k){tmp_len--;mm--;} 
        do{
            c = c + tmp_len ;
            if (s[i] != s[j]) mm--;

                i++;
                j++;

            tmp_len--;
            while (mm <=k && (j+tmp_len)<len)
            {
            if (s[i+tmp_len] != s[j+tmp_len])
                mm++;
            tmp_len++;
            }
            if(mm>k){tmp_len--;mm--;} 
        }while(tmp_len>0);

}
cout<<c<<endl;
return 0;
}

- Ajay Mittal

---

原本只有 "mismatches" 的拼写错误以及在 "+1" 的地方输成了 "+2" 的笔误。这已经被修复，快速实现能够匹配测试用例。 - Mike Housky