String/BoyerMoore.py

• View this file on GitHub
• Last update: 1970-01-01 00:00:00+00:00

Code

from collections import defaultdict

def BoyerMoore(s: str, t: str) -> bool:
    '''文字列 s の中に t が存在するかを判別する'''
    skip_table = defaultdict(lambda : -1)
    for i, j in enumerate(t[::-1]):
        if skip_table[j] == -1:
            skip_table[j] = i
    
    l_s = len(s)
    l_t = len(t)

    if l_s < l_t:
        return False
    else:
        i = l_t - 1
        cnt = 0
        while i < l_s:
            if s[i] == t[-1 - cnt]:
                cnt += 1
                i -= 1
            else:
                i += l_t if skip_table[s[i]] == -1 else skip_table[s[i]]
                cnt = 0

            if cnt == l_t:
                print(f'[{i + 1}, {i + l_t}] の区間に {t} が見つかりました。')
                return True
        
        return False

s = 'abcdefghijklmnopqrstuvwxyz'
t = 'def'
print(BoyerMoore(s, t))

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.5/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.5/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page