[algorithm] 두 개의 시퀀스가 ​​주어지면 한 쪽 끝과 다른 쪽 끝 사이의 최대 겹침을 찾으십시오.

Program / 글쓴이

다음 문제를 해결하려면 효율적인 (의사) 코드를 찾아야합니다.

이 (반드시 구별하지 않음) 정수의 시퀀스 감안 (a[1], a[2], ..., a[n])하고 (b[1], b[2], ..., b[n]), 최대 찾을 d그러한를 a[n-d+1] == b[1], a[n-d+2] == b[2], …,하고 a[n] == b[d].

이것은 숙제가 아닙니다. 가능한 한 많은 치수로 2 개의 텐서를 계약하려고 할 때 실제로 이것을 생각해 냈습니다. 효율적인 알고리즘이 O(n)있을지 모르지만 (아마 ?) 그렇지 않은 것을 생각 해낼 수는 없습니다 O(n^2). O(n^2)접근 방식에 분명 루프 것 d다음 항목에 대한 내부 루프는 최대 타격 할 때까지 필요한 조건을 확인 d. 그러나 나는 이것이 가능한 것보다 더 나은 것을 의심합니다.

답변

다음 과 같은 선형 시간 ( O (n) ) 알고리즘 인 z 알고리즘을 사용할 수 있습니다 .

문자열이 주어 S 길이 N은 Z 알고리즘 배열 생성 Z Z가 [I]는 최장부터 서브 스트링의 길이 [I] S
도의 접두사 S를

배열을 연결하고 ( b + a ) Z [i] + i == m + n 과 같이 첫 번째 i 까지 생성 된 생성 된 배열에서 알고리즘을 실행해야합니다 .

예를 들어, a = [1, 2, 3, 6, 2, 3] & b = [2, 3, 6, 2, 1, 0]의 경우 연결은 [2, 3, 6, 2, 1입니다. , 0, 1, 2, 3, 6, 2, 3]은 Z [i] + i = 12 = m + n을 만족시키는 Z [ 10] = 2를 산출 할 것이다 .

답변

O (n) 시간 / 공간 복잡성의 경우, 속임수는 각 하위 시퀀스에 대한 해시를 평가하는 것입니다. 배열을 고려하십시오 b.

[b1 b2 b3 ... bn]

Horner의 방법을 사용하면 각 하위 시퀀스에 대해 가능한 모든 해시를 평가할 수 있습니다. 기본 값을 선택하십시오 B(두 배열의 값보다 큼).

from b1 to b1 = b1 * B^1
from b1 to b2 = b1 * B^1 + b2 * B^2
from b1 to b3 = b1 * B^1 + b2 * B^2 + b3 * B^3
...
from b1 to bn = b1 * B^1 + b2 * B^2 + b3 * B^3 + ... + bn * B^n

이전 시퀀스의 결과를 사용하여 O (1) 시간에 각 시퀀스를 평가할 수 있으므로 모든 작업 비용은 O (n)입니다.

이제 배열이 Hb = [h(b1), h(b2), ... , h(bn)], Hb[i]에서 해시 b1까지를 bi.

배열에 대해서도 동일한 작업을 수행 a하지만 약간의 트릭을 사용하십시오.

from an to an   =  (an   * B^1)
from an-1 to an =  (an-1 * B^1) + (an * B^2)
from an-2 to an =  (an-2 * B^1) + (an-1 * B^2) + (an * B^3)
...
from a1 to an   =  (a1   * B^1) + (a2 * B^2)   + (a3 * B^3) + ... + (an * B^n)

한 시퀀스에서 다른 시퀀스로 이동할 때 이전의 전체 시퀀스에 B를 곱하고 새 값에 B를 곱한 값을 추가해야합니다. 예를 들면 다음과 같습니다.

from an to an =    (an   * B^1)

for the next sequence, multiply the previous by B: (an * B^1) * B = (an * B^2)
now sum with the new value multiplied by B: (an-1 * B^1) + (an * B^2)
hence:

from an-1 to an =  (an-1 * B^1) + (an * B^2)

이제 배열이 Ha = [h(an), h(an-1), ... , h(a1)], Ha[i]에서 해시 ai까지를 an.

이제 n에서 1까지의 Ha[d] == Hb[d]모든 d값을 비교할 수 있습니다. 값이 일치하면 답이 있습니다.

주의 : 이것은 해시 방법이며, 값이 클 수 있으며 빠른 지수 방법과 모듈 식 산술 을 사용해야 할 수도 있습니다 .이 방법은 충돌을 거의 일으키지 않으므로 완전히 안전하지 않습니다. 좋은 방법은 기본 B을 큰 소수 (적어도 배열에서 가장 큰 값보다 큼)로 선택하는 것입니다. 각 단계에서 숫자의 한계가 넘칠 수 있으므로주의해야합니다. 따라서 K각 작업 (( K보다 큰 소수 일 수 있음 )에서 (modulo ) 을 사용해야 B합니다.

이것은 두 개의 다른 시퀀스 가 동일한 해시를 가질 수 있지만 두 개의 동일한 시퀀스는 항상 동일한 해시를 갖음을 의미합니다.

답변

이것은 실제로 선형 시간, O (n) 및 O (n) 추가 공간 에서 수행 될 수 있습니다 . 입력 배열이 문자열이라고 가정하지만 필수는 아닙니다.

순진 방법은 것 – 일치 후 k 개의 동일한 문자 – 일치하지 않는 문자를 발견하고 돌아가 K-1 의 단위를 을 에 인덱스를 재설정 B , 그리고 거기에서 일치하는 프로세스를 시작합니다. 이것은 O (n²) 최악의 경우를 분명히 나타냅니다 .

이 역 추적 과정을 피하기 위해 마지막 k-1 문자 를 스캔하는 동안 b [0] 문자를 찾지 못한 경우 되돌아가는 것이 유용하지 않음을 알 수 있습니다 . 우리가하면 한 그 문자를 찾을 수 있다는 점에서 경우에, 그 위치로 되돌아 만, 유용 할 수 k는 서브 스트링으로 크기 우리는 주기적으로 반복했다.

예를 들어, 우리가 어딘가에 “ABCABC”부분 문자열 보면 , 및 b는 “abcabd”이며, 우리의 마지막 문자를 찾을 b는 일치하지 않는, 우리는 성공적으로 일치하는 두 번째 “A”에서 시작 수 있음을 고려해야합니다 비교를 계속하기 전에 현재 색인을 b에서 뒤로 이동해야합니다 .

그런 다음 문자열 b 를 기반으로 일부 전처리를 수행 하여 불일치가있는 경우를 확인하는 데 유용한 b의 역 참조를 기록 합니다. 예를 들어, b 가 “acaacaacd” 인 경우 이러한 0 기반 역 참조 (각 문자 아래에 있음)를 식별 할 수 있습니다.

index: 0 1 2 3 4 5 6 7 8
b:     a c a a c a a c d
ref:   0 0 0 1 0 0 1 0 5

우리가 예를 들어, 동일 “을 acaacaaca”최초의 불일치는 마지막 문자에 발생합니다. 위의 정보는 “acaac”이 일반적이기 때문에 알고리즘이 b 에서 인덱스 5 로 되돌아 가도록 지시합니다 . 그리고 만에 현재 인덱스를 변경하여 B 우리의 현재 인덱스의 일치를 계속할 수 . 이 예에서는 최종 캐릭터의 일치가 성공합니다.

이것으로 우리는 검색을 최적화하고있는 인덱스 확인 할 수 있습니다 A는 항상 앞으로 진행 할 수 있습니다.

다음은 해당 언어의 가장 기본적인 구문 만 사용하여 JavaScript로 해당 아이디어를 구현 한 것입니다.

function overlapCount(a, b) {
    // Deal with cases where the strings differ in length
    let startA = 0;
    if (a.length > b.length) startA = a.length - b.length;
    let endB = b.length;
    if (a.length < b.length) endB = a.length;
    // Create a back-reference for each index
    //   that should be followed in case of a mismatch.
    //   We only need B to make these references:
    let map = Array(endB);
    let k = 0; // Index that lags behind j
    map[0] = 0;
    for (let j = 1; j < endB; j++) {
        if (b[j] == b[k]) {
            map[j] = map[k]; // skip over the same character (optional optimisation)
        } else {
            map[j] = k;
        }
        while (k > 0 && b[j] != b[k]) k = map[k];
        if (b[j] == b[k]) k++;
    }
    // Phase 2: use these references while iterating over A
    k = 0;
    for (let i = startA; i < a.length; i++) {
        while (k > 0 && a[i] != b[k]) k = map[k];
        if (a[i] == b[k]) k++;
    }
    return k;
}

console.log(overlapCount("ababaaaabaabab", "abaababaaz")); // 7

스 니펫 확장

중첩 while루프 가 있지만 n 보다 총 반복 횟수가 더 적습니다 . 이것은 k 값이 while신체 에서 엄격하게 감소하고 음수가 될 수 없기 때문입니다. k++이러한 감소를위한 충분한 공간을 제공하기 위해 여러 번 실행 된 경우에만 발생할 수 있습니다 . 따라서 대체로 while신체보다 많은 신체적 처형이있을 수 없으며 k++후자는 분명히 O (n)입니다.

완료하려면 여기에서 위와 동일한 코드를 찾을 수 있지만 대화식 스 니펫에서 직접 문자열을 입력하고 대화식으로 결과를 볼 수 있습니다.

코드 스 니펫 표시

답변