Common Childのプログラミング チャレンジでは、一般的な Longest Common Substring 問題とは異なるアプローチを取りました。コードは
#include <cmath>
#include <cstdio>
#include <vector>
#include<string>
#include <iostream>
#include <algorithm>
using namespace std;
void max(string a,string b,int n)
{
int count=0,x=-1,prev=0,i,j,k;
for(i=0;i<n;i++)
{
x=-1;
for(j=i;j<n;j++)
{
for(k=x+1;k<n;k++)
{
if(a[j]==b[k])
{
count++;
x=k;
break;
}
}
}
if(prev<count)
{
prev=count;
}
count=0;
}
cout<<prev;
}
int main() {
string a,b;
int n;
cin>>a;
cin>>b;
n=a.length();
max(a,b,n);
return 0;
小さい TestCases を使用すると、解決策を得ることができますが、より長いテストケースの解決策を得ることができません。
私がしたことは
入力: ABCDEF - FBDAMN とします - コードに挿入されるので b とします。出力: 2. BD は部分文字列です。
したがって、ここで行っているのは、a の各部分文字列の一致可能な部分文字列をチェックし、最大のものを出力することです。すなわち。ここで最も外側のループを表す ABCDEF、BCDEF、CDEF、DEF、EF、F の部分文字列 (ループ i)
2 番目のループは、文字列内の各文字に一致します。(1...n)、(2...n)、(3...n)、...、(n) を反復します。つまり、i が指定する文字から開始します。
次に、3 番目のループが文字列 B 全体を繰り返し処理して、a[j] が B の文字と一致するかどうかを確認し、一致する場合はカウントを増やします。
部分文字列から文字を削除することしかできないため、ごちゃ混ぜにすることはできません。つまり、各文字は両方の文字列で同じ相対的な順序である必要があるため、前の文字が見つかった後、x を使用して B を検索しています。
ドライランは例のようになります（0からn-1までの配列）
a= abcdef b= fbdamn
i=0 の場合 - 文字列全体が一致する abcdef
x=-1 なので、k は 0 から n-1 まで繰り返すので、a=f? a=b? a=d? a=a? カウント = カウント + 1; したがって、x は 3(a の位置) として設定されます。A の a の後の要素は、B の a の後にしか出現しないため、x=3 です。したがって、k は 4 から 5 まで繰り返されます。 b=m? b=n? c=m?c=n? ... ... ... ...
以前のカウントよりも大きい場合は、以前のカウントの値を保存します。したがって、maxcount=count で、count を 0 にリセットし、位置を x=-1 にリセットします。
i=1 ie string = BCDEF k from 0 to n だから、B=F? b=b? count=count+1 // 1 になる x を 1(B の位置) とする k 2 から nc=d? c=a?c=m?c=n? k は 2 から nd=d まで? count = count+1 // 2 になる x は 2 k として 3 から ne=a?e=m?e=n? まで 3 から nf=a?f=m?f=n? までの k 次に、最大カウント (コード内の prev) が現在のカウントより大きい場合、最大カウント = カウント、リセット カウント = 0、x=-1; CDEF、DEF、EF、Fの場合、ここの最大部分文字列は2になります。
長いテストケースではなく、短いテストケースで機能します。
それが機能するテストケースは次のとおりです。
OUDFRMYMAW AWHYFCCMQX
出力2付
機能しません
WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC
正しい出力は15で、私の出力は10です。誰かが私にどこで間違いを犯しているのか説明できますか