[python]伯準16916-部分文字列

Overview
BOJ 16916部分文字列Python解答
分類:String(文字列)
質問ページ
https://www.acmicpc.net/problem/16916
プールコード1

s, p = (input().rstrip() for _ in range(2))
print([0, 1][p in s])

最も簡単な解答.
inメソッドを使用して、p文字列がs文字列にあるかどうかを決定します.
プールコード2

s, p = (input().rstrip() for _ in range(2))
print([0, 1][s.__contains__(p)])

文字列ライブラリの__contains__(str)メソッドの使用
プールコード3-KMPアルゴリズム

from sys import stdin
from typing import List


def make_table(p: str) -> List[int]:
    table = [0] * len(p)

    j = 0
    for i in range(1, len(table)):
        while j > 0 and p[i] != p[j]:
            j = table[j - 1]

        if p[i] == p[j]:
            j += 1
            table[i] = j

    return table


def kmp(s: str, p: str, table: List[int]) -> bool:
    i, j = 0, 0

    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = table[j - 1]

        if s[i] == p[j]:
            j += 1
            if j == len(p):
                return True

    return False


def main():
    s = stdin.readline().rstrip()
    p = stdin.readline().rstrip()

    table = make_table(p)
    print([0, 1][kmp(s, p, table)])


if __name__ == "__main__":
    main()

KMPアルゴリズムを用いて解く.
String Matchingアルゴリズムの1つであるKnuth−Morris−Prattアルゴリズムを用いた.
まずFailure関数(上のコードではmake_table())を計算し,これに基づいて文字列sにパターンpが存在するか否かを探索する.
Failure関数で計算した時間複雑度はO(m)であり,KMPアルゴリズムによるモード探索はO(m＋n)の時間複雑度を持つ.
解コード4-Boyer Mooreアルゴリズム

from sys import stdin
from typing import List


# character jump에 사용하기 위하여 p에서 각 문자 위치를 저장한 테이블 생성 
# (Last-Occurrence Function)
def set_table(p: str) -> List[int]:
    table = [-1] * 26
    for i in range(len(p) - 1, -1, -1):
        if table[ord(p[i]) - 97] == -1:
            table[ord(p[i]) - 97] = i
    return table


def character_jump(s: str, p: str, s_idx: int, p_idx: int, table: List[int]) -> int:
    l = table[ord(s[s_idx]) - 97]
    if l >= 0:
        return s_idx + len(p) - min(p_idx, 1 + l)
    else:
        return s_idx + len(p)


def boyer_moore(s: str, p: str) -> bool:
    i, j = len(p) - 1, len(p) - 1
    table = set_table(p)

    while i < len(s):
        if s[i] == p[j]:
            if j == 0:
                # i 번째에서 String Match
                return True
            else:
                i -= 1
                j -= 1
        else:
            i = character_jump(s, p, i, j, table)
            j = len(p) - 1

    return False


def main():
    s = stdin.readline().rstrip()
    p = stdin.readline().rstrip()

    print([0, 1][boyer_moore(s, p)])


if __name__ == "__main__":
    main()

Boyer-Mooreアルゴリズムに適用されるString Matching技術.これは実際のBoyer‐Mooreアルゴリズムとは異なるかもしれない.
採点結果がタイムアウトした.
このアルゴリズムには、次の2つのヒントがあります.
1.Looking-Grass Heuritic:文字列sとパターンpを比較する場合、pの後ろから比較します.
2.Character-jumpイニシアチブ:不一致が発生した場合、次の比較位置を探す方法.一致しない文字列sの文字がモードpに存在する場合、その位置にジャンプし、そうでなければpの長さにジャンプする.このため、Last-Occurence Functionは、Boyer−Mooreアルゴリズムを使用する前に実装される.
試験−機能はO(m＋s)の時間的複雑さを持ち,Boyer−MooreアルゴリズムはO(nm＋s)の時間的複雑さを持つことが分かった.sは文字列タイプの個数であり,本題の入力は小文字のみであるため26である.通常、Boyer-Mooreアルゴリズムは、英語のような文字列を検索する際に高速なパフォーマンスを示します.しかし、以下の最悪の場合、長い時間がかかります.

s = aaa ... a
p = baaa

したがって、画像、DNA塩基配列においてパターンマッチング法を用いてこのアルゴリズムを用いると、性能が低下する可能性がある.