Common Child의 프로그래밍 과제에서 일반적인 일반 하위 문자열 문제와 다른 접근 방식을 사용했습니다. 코드는가장 긴 일반 하위 문자열 접근법
#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;
작은 테스트 케이스를 가지고 있습니다. 해결책을 얻을 수는 있지만, 긴 테스트 케이스는 솔루션을 얻을 수 없습니다. 내가 무슨 짓을
는
입력 : ABCDEF - 그것은 FBDAMN하자 -이 코드에 삽입 될 때, 그것은 ㄱ합시다. 출력 : 2. ie. BD가 하위 문자열이됩니다.
그래서 여기서는 각각 부분 문자열에 대해 일치하는 부분 문자열을 확인하고 가장 큰 값을 인쇄합니다. 즉. 여기에서 가장 바깥 쪽 루프를 의미하는 BCDEF, CDEF, DEF, EF, F (루프 i)
이제 두 번째 루프는 문자열 ie의 각 문자와 일치합니다. (1 ... n), (2 ... n), (3 ... n), ..., (n)에 대해 을 반복합니다. 이것은 문자 에서 시작한다는 것을 의미합니다.
이제 세 번째 루프가 문자열 B 전체를 반복하여 [A] [B]가 B의 문자와 일치하는지 확인합니다. 그렇다면 숫자가 증가합니다.
우리는 단지 그것을 뒤범벅 문자열에서 문자를 제거 할 수 없기 때문에, 즉, 각 문자는 이전의 문자가 X를 사용하여, 발견 된 후 모두 문자열에서 같은 상대하기 위해, 나는 B를 검색하고 있어야합니다.
드라이 실행
(0 내지 N-1로 배열)을, 예를 들면 같은 것 A = ABCDEF B = fbdamn
난 = 0 때 - 전체 문자열 ABCDEF 유사한지고x = -1 그래서 k는 0에서 n-1까지 반복합니다. 따라서 a = f? a = b? a = d? a = a? 카운트 = 카운트 +1; 따라서 x는 3으로 설정됩니다 (a의 위치). a in a 이후의 요소는 이 a에서 B 이후에만 발생하므로 x = 3입니다. 그러므로 k는 4에서 5로 반복한다. b = m? b = n? c = m ㆍ c = n? .... ... ...
이전에 보다 큰 숫자가 있으면 이전 계수의 값을 저장합니다. 그래서 maxcount = count 다음에 카운트를 0으로 재설정하고 위치 x = -1로 재설정하십시오.
i = 1 즉, 문자열 = 0에서 n까지의 BCDEF k 따라서, B = F? b = b? count = count + 1 // 이 1이 될 때 x는 2에서 nc = d까지 1 (B의 위치) k로 설정됩니다. c = a ㆍ c = m ㆍ c = n? k가 2에서 n까지 d = count = count + 1 //는 2가된다 .3 × 2 = 3 × 2 = 3 × 3 = k는 3에서 n까지이다 .f = a · f = m · f = n? 최대 카운트 ( 코드에서 prev)가 현재 카운트보다 크면 maxcount = count, 재설정 카운트 = 0, x = -1; CDEF, DEF, EF, F의 경우와 같습니다. 여기에 따라서 최대 값 문자열이됩니다. 2
더 긴 테스트 케이스에 대해서는 작동하지 않습니다.그것이 작동
테스트 사례는 다음과 같습니다
OUDFRMYMAW AWHYFCCMQX 출력
2
않아요 일
WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC
들어정확한 출력은 이고 내 출력은 입니다. 누구나 어디에서 나는 다음과 같다 예견
나는 이것에 대한 닫는 표를 이해하지 못한다 : 질문은 완전하고 완벽하다. – dasblinkenlight