Boyer-Mooore 문자열 검색 알고리즘에서 두 번째 (Mis-Match) 테이블 계산

Question

Boyer-Moore 알고리즘이 최악의 선형이 되려면 Mist-Match 테이블의 계산은 O (m)이어야합니다. 그러나 순진한 구현은 모든 접미사 O (m)를 통해 루프를하고 접미사가 갈 수 있다는 것의 모든 위치는 평등을 확인할 수 있습니다 ...³)!

아래는 순진한 구현입니다 테이블 빌딩 알고리즘. 그렇다면이 질문은 다음과 같은이 알고리즘의 런타임을 O (M)로 어떻게 개선 할 수 있습니까?

def find(s, sub, no):
    n = len(s)
    m = len(sub)

    for i in range(n, 0, -1):
        if s[max(i-m, 0): i] == sub[max(0, m-i):] and \
            (i-m < 1 or s[i-m-1] != no):
            return n-i

    return n

def table(s):
    m = len(s)
    b = [0]*m

    for i in range(m):
        b[i] = find(s, s[m-i:], s[m-i-1])

    return b

print(table('anpanman'))

마음을 쉬기 위해 이것은 숙제가 아닙니다. 누구나 개선을위한 아이디어를 게시 할 때 개정을 추가하겠습니다.

Answer 1

"Good-Suffix Heuristics에 대한 전처리"에 따른 코드 이 페이지 O (N) 시간으로 Good-Suffix 테이블을 작성합니다. 또한 코드의 작동 방식을 설명합니다.