3

ブルートフォースを使用して解決できましたが、この問題を解決しようとしていますが、次の最適化されたアルゴリズムでは、一部のテストケースで誤った結果が得られます。試してみましたが、コードの問題を見つけることができませんでした助けて。

問題 : 文字列 S と整数 K が与えられたとき、S1 と S2 の長さが等しく、Mismatch(S1, S2) <= K である部分文字列 (S1,S2) のペアの数に等しい整数 C を見つけます。ここで、不一致関数は次のとおりです。を以下に定義します。

ミスマッチ関数

Mismatch(s1,s2) は、S1 と S2 の文字が異なる位置の数です。たとえば、mismatch(bag,boy) = 2 (2 番目と 3 番目の位置に不一致があります)、mismatch(cat,cow) = 2 (2 番目と 3 番目の位置に不一致があります)、Mismatch(London, Mumbai) = 6 (2 つの文字列のすべての位置の文字が異なるため)。ロンドンの最初の文字は「L」ですが、ムンバイでは「M」です。ロンドンの 2 番目の文字は「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

2 つのエラーがあります。初め、

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

する必要があります

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

そうでなければ、

str[j+r]

ある時点で、null ターミネータを超えた文字 (つまり、文字列の末尾を超えた部分) の比較を開始します。最大r値は、jインデックスから最後の文字までの残りの文字数です。

第二に、書く

str[i+r]

と

str[j+r]

は常に少なくとも であるため、i番目とj番目の文字の比較をスキップします。あなたは書くべきですr1

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 に答える