두 개의 큰 배열에서 가장 긴 문자열 일치를 얻기 위해 사용할 알고리즘은 무엇입니까?

Question

문제는 설명하기 쉽습니다. 우리는 두 개의 큰 배열 (32 비트 정수 값)을 가지며 지정된 수의 연속 위치 (n) 위에 모든 공통 시퀀스를 찾아야합니다. N = 3 배열과 비교하는 경우, 예를 들어

같습니다

a = [1, 3, 5, 7, 3, 2, 7, 4, 6, 7, 2, 1, 0, 4, 6] 
b = [2, 5, 7, 3, 2, 3, 4, 5, 6, 3, 2, 7, 4, 6, 0] 

가 algoritmh 반환한다 두 배열 :

r0 = [5, 7, 3, 2] 
r1 = [3, 2, 7, 4, 6] 

(이상, 제 배열의 상대적인 위치 및 연속 한 바이트 수가 일치한다).

나는 시작하는 것이 좋은 점은 Longest Common Substring Algorithm이라고 생각하지만, 아마도 누구나 내 문제에 더 잘 맞는 알고리즘을 알고있을 것입니다. 내가 제대로 이해하고 N, 다음 I'de가 보이어 - 무어의 검색 알고리즘의 변형을 사용하여 시퀀스의 최소 크기 인 경우

Answer 1

나는 접미사 트리를 사용하여 LCS를 찾기위한 알고리즘을 생각한다 완벽한 착용감입니다. 동일한 방식으로 접미어 트리를 작성하지만 최종 단계에서는 두 문자열 모두에 대해 하위 노드가있는 가장 깊은 노드를 찾지 않습니다. 두 문자열에 모두 하위 노드가있는 n 이상의 심도를 가진 모든 노드를 찾고 있습니다.

Answer 2

은 (http://en.wikipedia.org/wiki/Boyer_moore)

Answer 3

내가 알고있는 위키피디아 페이지의 알고리즘이 원하는 것을 거의 정확하게 수행한다고 생각합니다. 가장 긴 대답을 유지하는 것보다 특정 크기 이상의 모든 대답을 유지하도록 수정해야합니다. 예를 들어, 해당 페이지의 동적 프로그래밍 솔루션은 다음과 같이 수정 될 수 있습니다.

function LCSubstr(S[1..m], T[1..n], min_size) 
    L := array(1..m, 1..n) 
    ret := {} 
    for i := 1..m 
     for j := 1..n 
      if S[i] = T[j] 
       if i = 1 or j = 1 
        L[i,j] := 1 
       else 
        L[i,j] := L[i-1,j-1] + 1 
       if L[i,j] >= min_size 
        ret := ret ∪ {S[i-z+1..z]} 
    return 

이렇게 작성된 것으로 접두어와 가장 긴 일치 항목이 포함됩니다. 그것들은 L로 발견 된 문자열을 추적하고 확장이 있음을 발견했을 때 반환 세트에서 접두어를 제거함으로써 걸러 낼 수 있습니다.