検索文字列

文字列検索は、ある文字列に他の文字列が含まれているかどうかを確認し、含まれている場合はその位置を検索することを意味します.
テキスト
検索された文字列をモードと呼びます.

Brute-Force

単純拡張線形検索アルゴリズム

テキストの最初の文字から4文字がパターンに一致していることを確認します:

が一致しない場合、パターンを右に1つ押して、一致するまで

を検索します.

は、検査された位置を覚えていないため、再スキャンが必要であり、効率が悪い.

def bf_match(txt: str, pat: str) -> int:
    """브루트 포스법으로 문자열 검색"""
    pt = 0  # txt(텍스트)를 따라가는 커서
    pp = 0  # pat(패턴)를 따라가는 커서

    while pt != len(txt) and pp != len(pat):
        if txt[pt] == pat[pp]:
            pt += 1
            pp += 1
        else:
            pt = pt - pp + 1
            pp = 0

    return pt - pp if pp == len(pat) else -1

文字列検索用Python標準ライブラリ

# 포함 여부 확인
ptn in txt
ptn not in txt

# find, index 계열 함수
str.find(sub, start, end)
# 문자열 str의 start, end에 sub이 포함되면 그중에 가장 작은 인덱스 반환, or -1
str.rfind(sub, start, end)
# 문자열 str의 start, end에 sub이 포함되면 그중에 가장 큰 인덱스 반환, or -1

str.index()
#find()와 같은 기능
str.rindex()
#rfind()와 같은 기능
다만 index()계열의 method는 발견되지 않을 시에 -1이 아닌 ValueError 내보냄


#with 계열 함수
str.startswith(prefix, start, end)
# 문자열이 prefix로 시작하면 True

str.endswith(suffix, start, end))
# 문자열이 suffix로 끝나면 True

KMP

単純な形式で表示するのではなく、結果をより効果的にチェックできるアルゴリズムです.
KMPアルゴリズム

は、部分的に一致しない限り、マッチングモードにおいて最大長の境界を見つける.
失敗関数
モード「ababc」規格

「a」に一致する接頭辞/接尾辞の最大長:0(なし)

abに一致する接頭辞/接尾辞の最大長:0(なし)

「aba」に一致する接頭辞/接尾辞の最大長:1(「a」)

ababに一致する接頭辞/接尾辞の最大長:2(ab)

ababcに一致する接頭辞/接尾辞の最大長:0(なし)

つまり、正しい部分に移動した失敗関数の値!![]

def kmp_match(txt: str, pat: str) -> int:
    """KMP법에 의한 문자열 검색"""
    pt = 1  # txt를 따라가는 커서
    pp = 0  # pat를 따라가는 커서
    skip = [0] * (len(pat) + 1)  # 건너뛰기 표

    # 건너뛰기 표 만들기
    skip[pt] = 0
    while pt != len(pat):
        if pat[pt] == pat[pp]:
            pt += 1
            pp += 1
            skip[pt] = pp
        elif pp == 0:
            pt += 1
            skip[pt] = pp
        else:
            pp = skip[pp]

    # 검색하기
    pt = pp = 0
    while pt != len(txt) and pp != len(pat):
        if txt[pt] == pat[pp]:
            pt += 1
            pp += 1
        elif pp == 0:
            pt += 1
        else:
            pp = skip[pp]

    return pt - pp if pp == len(pat) else -1

どうやって?

Boyer-Mooreアルゴリズム(Boyer-Mooreアルゴリズム)

通常、文字列は、後の部分を使用して一致しない確率が前の部分より高い性質を有する.

不要なものをスキップして、素早く検索!

図案右端文字と本文を比較することにより、に一致するか否かを判断する
文字がパターンに存在しない場合は、パターンの長さに従って移動します.

テキスト文字はモードに存在するが、中間が一致しない場合、右端からその文字のセル数まで数え、それに応じて移動する.

def bm_match(txt: str, pat: str) -> int:
    """보이어 무어법에 의한 문자열 검색"""
    skip = [None] * 256  # 건너뛰기 표

    # 건너뛰기 표 만들기
    for pt in range(256):
        skip[pt] = len(pat)
    for pt in range(len(pat)):
        skip[ord(pat[pt])] = len(pat) - pt - 1

    # 검색하기
    while pt < len(txt):
        pp = len(pat) - 1
        while txt[pt] == pat[pp]:
            if pp == 0:
                return pt
            pt -= 1
            pp -= 1
        pt += skip[ord(txt[pt])] if skip[ord(txt[pt])] > len(pat) - pp \
              else len(pat) - pp

    return -1