문자열 알고리즘
KMP (Knuth-Morris-Pratt)
패턴 매칭. O(n+m). 불일치 시 앞으로 돌아가지 않는다.
def kmp(text, pattern):
def build_failure(p):
fail = [0] * len(p)
j = 0
for i in range(1, len(p)):
while j > 0 and p[i] != p[j]:
j = fail[j-1]
if p[i] == p[j]:
j += 1
fail[i] = j
return fail
fail = build_failure(pattern)
matches = []
j = 0
for i, ch in enumerate(text):
while j > 0 and ch != pattern[j]:
j = fail[j-1]
if ch == pattern[j]:
j += 1
if j == len(pattern):
matches.append(i - j + 1)
j = fail[j-1]
return matches라빈-카프 (Rabin-Karp)
해시 기반 패턴 매칭. 평균 O(n+m).
def rabin_karp(text, pattern):
BASE, MOD = 256, 10**9 + 7
n, m = len(text), len(pattern)
h = pow(BASE, m-1, MOD)
ph = th = 0
for i in range(m):
ph = (BASE * ph + ord(pattern[i])) % MOD
th = (BASE * th + ord(text[i])) % MOD
matches = []
for i in range(n - m + 1):
if ph == th and text[i:i+m] == pattern:
matches.append(i)
if i < n - m:
th = (BASE * (th - ord(text[i]) * h) + ord(text[i+m])) % MOD
return matches최장 회문 부분 문자열 (Manacher)
O(n)으로 모든 회문 탐색.
def manacher(s):
t = '#' + '#'.join(s) + '#'
n = len(t)
p = [0] * n
c = r = 0
for i in range(n):
mirror = 2 * c - i
if i < r:
p[i] = min(r - i, p[mirror])
while i + p[i] + 1 < n and i - p[i] - 1 >= 0 and \
t[i + p[i] + 1] == t[i - p[i] - 1]:
p[i] += 1
if i + p[i] > r:
c, r = i, i + p[i]
# 가장 긴 회문 길이
max_len = max(p)
return max_lenZ 알고리즘
각 위치에서 시작하는 최장 공통 접두사 길이 배열. O(n).
def z_function(s):
n = len(s)
z = [0] * n
z[0] = n
l = r = 0
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l, r = i, i + z[i]
return z아나그램 / 해시 응용
from collections import Counter
# 아나그램 판별
def is_anagram(s, t):
return Counter(s) == Counter(t)
# 슬라이딩 윈도우로 아나그램 모든 위치 찾기
def find_anagrams(s, p):
result = []
pc = Counter(p)
wc = Counter(s[:len(p)])
if wc == pc: result.append(0)
for i in range(len(p), len(s)):
wc[s[i]] += 1
old = s[i - len(p)]
wc[old] -= 1
if wc[old] == 0: del wc[old]
if wc == pc: result.append(i - len(p) + 1)
return result