c - 最多 K 个不匹配的子串？

Question

我正在尝试解决这个问题，虽然我可以使用蛮力解决它，但是以下优化算法为我提供了一些测试用例的错误结果。我尝试了但无法找到代码的问题，任何人都可以帮助我。

问题:给定一个字符串 S 和整数 K，找到整数 C，它等于子串对的数量 (S1,S2) 使得 S1 和 S2 具有相等的长度并且 Mismatch(S1, S2) <= K 其中定义了不匹配函数下面。

失配函数

Mismatch(s1,s2) 是 S1 和 S2 中字符不同的位置数。例如mismatch(bag,boy) = 2(第二个和第三个位置不匹配)，mismatch(cat,cow) = 2(同样，第二个和第三个位置不匹配)，Mismatch(London, Mumbai) = 6(因为两个字符串中每个位置的字符都不同)。伦敦的第一个字符是“L”，而在孟买是“M”，伦敦的第二个字符是“o”，而在孟买是“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. 测试用例(通过以上代码)

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

2. 测试用例(上述代码失败)

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

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++)