3

我正在尝试解决这个问题，尽管使用蛮力我能够解决它，但是下面的优化算法给我一些测试用例的错误结果。我试过但无法;找不到代码的问题可以任何机构帮我。

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

失配函数

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
4

3 回答 3

1

你有两个基本错误。当 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参与。

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

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

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

注意：您询问了一种更快的方法。有一个，但编码更多。在起始索引值之间的差异增量上进行外循环。(0<delta<len) 然后，计算所有可接受的匹配项，例如：

计数 = 0;
对于 delta = 1 到 len-1
    设置 i=0; j=增量；不匹配=0；r=0；
    而 j < len
        .. 找到第 k 个不匹配，或者 str 的结尾：
        而不匹配 < k 和 j+r<len
            如果 str[i+r] != str[j+r] then mismatches=mismatches+1
            r = r+1
        结束时
        .. 扩展 r 以覆盖任何尾随匹配：
        而 j+r<len 和 str[i+r]==str[j+r]
            r + r+1
        结束时

        .. 到达这里 r 是从 str[i] 开始的最长字符串对
        .. 和 str[j] 不超过 k 个不匹配。这个循环将添加 (r)
        .. 计数并将 i,j 向右推进一个空格而不重新计数
        ..里面的字符不匹配。相反，如果不匹配被丢弃
        .. 前面，然后 mismatches 减 1。
        重复
            计数 = 计数 + r
            如果 str[i] != str[j] 那么 mismatches=mismatches-1
            i = i+1, j = j+1, r = r-1
        直到不匹配 < k
    万一
结束时

那是伪代码，也是伪正确的。一般的想法是在一次遍历中比较所有起始索引相差 (delta) 的子字符串，开始和左侧，并增加子字符串长度 r 直到到达源字符串的末尾或已经看到 k+1 个不匹配。也就是说，str[j+r] 要么是字符串的结尾，要么是右子字符串中的骆驼背断不匹配位置。这使得从 str[i] 和 str[j] 开始的 r 个子串具有 k 个或更少的不匹配。

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

应该很容易看出，在每个循环中，要么 r 增加 1，要么 j 增加 1，并且 (j+r) 保持不变。j 和 (j+r) 都会在 O(n) 时间内达到 len，所以整个过程是 O(n^2)。

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

重新编辑：修复了评论错误。重新编辑：算法中有更多拼写错误，主要是拼写错误并增加 2 而不是 1。

于 2013-08-14T11:34:55.647 回答
1

你有两个错误。第一的，

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

应该

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

否则，

str[j+r]

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

二、写作

str[i+r]

和

str[j+r]

跳过i第 th 和jth 字符的比较，因为r总是至少1。你应该写

for(r=0;r<len-j;r++)
于 2013-08-14T09:19:11.210 回答
0

@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;
}
于 2013-08-16T06:56:27.760 回答