다른 문자열에서 최대 비슷한 하위 문자열 찾기

Question

두 개의 문자열 n1과 n2가 제공됩니다. 이것들과 함께, 나는 숫자 K를 제공 받고있다.

이제 나는 다음과 같은 3 개의 수 - i, j, l을 찾아야한다 : 길이가 l 인 인덱스 i에서 시작하는 부분 문자열은 atmost을 갖는다. K는 n2의 인덱스 j에서 길이 l 인 부분 문자열과 일치하지 않습니다. 그리고 이것은 K 차이와 가능한 최대 부분 문자열입니다.

예해야 명확 :
N1 = 브리즈
N2 = 토리노
K = 2
다음 출력 같아야
I = 2
J = 1
L = 4
[ "briz"와 "orin"은 2 개의 비 유사성을 가지고 있기 때문에]

현재 접근법 : n1의 각 하위 시퀀스에 대해 n2에서 최대 공통 부분 시퀀스를 찾으려고합니다 (atmo 세인트 K 불일치). 이 문제를보다 효율적으로 해결할 수있는 더 나은 방법을 가진 사람이 있습니까? I는 LCS 같은 동적 프로그래밍을 할 수 있다고 생각

Answer 1

, S1에서 I에서

공통 (I, J, L, K) = 최대 문자열 스트랫 (대 길이 (L)를 가지며, 가장 유전율이 맞지 모든 < = n, j < = n, l < = n, k < = K) 먼저 평범한 (i, j, l, 0)을 계산해야합니다. 위한

K> 0!

STR1는 [내가 LT +] 경우 = STR2 [J 모든 1 ≤ ≤ L-1 K-1 & & KF ≤ t ≤ F 용

간단한 있다는 것을 보장된다

common(i,j,l,k) = maximum{common(i,j,l-t-1,k-f) + common(i,j,t,f-1)} 
else 
    common(i,j,l,k) = maximum{common(i,j,l-t,k-f) + common(i,j,t,f)} 

Answer 2

+ LT] 무엇? 용액이 경우에 일어난다 :

N1 = qertyq

N2 = quertac

K = 2

알고리즘 여러 솔루션이있을 것이다 0,0,6

1,1,5

2,2,4-

3,3,3-

2,2,2-

당신은 내가 사이드 옳다고 생각하는 문제에 대한 해결책은 단 하나입니다 보장하는 경우, 당신은 그것을

Answer 3

를 해결하기 위해 동적 프로그래밍을 사용해야합니다

다음은 간단한 bruteforce입니다. 가능한 i와 j 쌍의 길이를 계산합니다. 복잡성은 O (n1.length * n2)입니다.length * min (n1.length, n2.length)). 두 문자열의 길이가 n 일 때 O (n)입니다. 여기

for (i = 0; i < n1.length; i++) 
{ 
    for (j = 0; j < n2.length; j++) 
    { 
     errors = 0 
     len = 0 

     while (errors <= k && i+len < n1.length && j+len < n2.length) 
     { 
      if (n1[i+len] != n2[j+len]) errors++ 
      if (errors <= k) len++ 
     } 

     if (len > best) update best 
    } 
} 

는 i와 j 사이의 모든 가능한 오프셋 통과보다 효율적인 해결책이 오프셋은 다음 정확하게 K 오류로 유지 따라 문자열을 (이동 저거 K 오류가있는 문자열을 설정) 각 지점에서 길이를 관찰합니다. 복잡성은 O ((n1.length + n2.length) * min (n1.length, n2.length))입니다. 두 문자열의 길이가 n 인 경우이 값은 O (n)입니다.

for (offset = -n1.length; offset < n2.length; offset++) 
{ 
    // j is equal to (i + offset) 

    start = (offset > 0) ? 0 : -offset 
    stop = min(n1.length, n2.length - offset) 

    errors = 0 
    e = start // e is one past the end of the sequence, so l = e - i 

    for (i = start; i < stop; i++) 
    { 
     // move the end of the substring to maintain exactly k errors 
     while (e < stop && (errors < k || n1[e] == n2[e+offset])) 
     { 
      if (n1[e] != n2[e+offset]) errors++ 
      e++ 
     } 

     if (e - i > best) update best 

     if (n1[i] != n2[i+offset]) errors-- 
    } 
}