문자열 코드
노트의 개념을 Python 3로 옮긴 코드다. 표준 라이브러리만 쓰고, 파일 끝의 assert 예제가 그대로 실행된다. 복사해 python3 파일이름.py로 돌려 보자.
단순 탐색
"""단순 탐색: 패턴을 본문의 모든 자리에 대 보며 왼쪽부터 글자를 비교한다.
시간: 최악 O(nm) (n = 본문 길이, m = 패턴 길이), 보통의 글에서는 O(n)에 가깝다
공간: O(1) — 찾은 자리 목록을 빼면 추가 메모리가 없다
"""
def naive_search(text: str, pattern: str) -> tuple[list[int], int]:
"""pattern이 나오는 시작 위치 목록과 글자 비교 횟수를 돌려준다."""
matches: list[int] = []
comparisons = 0
for shift in range(len(text) - len(pattern) + 1):
matched = 0
while matched < len(pattern):
comparisons += 1
if text[shift + matched] != pattern[matched]:
break
matched += 1
if matched == len(pattern):
matches.append(shift)
return matches, comparisons
if __name__ == "__main__":
assert naive_search("ABABAABABAC", "ABABAC") == ([5], 20)
assert naive_search("AABAACAABA", "AABA") == ([0, 6], 17)
# 최악: 자리마다 끝 글자에서야 틀린다 → (n - m + 1) × m번
assert naive_search("AAAAAAAA", "AAAB") == ([], 20)
# 겹치는 일치도 모두 찾는다
assert naive_search("AAAA", "AA")[0] == [0, 1, 2]
assert naive_search("AB", "ABC") == ([], 0)
assert naive_search("", "A") == ([], 0)
print("ok")KMP 실패 함수
"""KMP 실패 함수(prefix function): 앞 i + 1글자의 접두사이면서 접미사인 가장 긴 진부분 문자열의 길이.
시간: O(m) — k는 한 번에 1씩만 늘고 while에서 줄기만 하므로 줄어드는 총량이 늘어난 총량을 넘지 못한다
공간: O(m) — 표 하나
"""
def failure_function(pattern: str) -> list[int]:
"""pattern의 실패 함수 표를 돌려준다."""
failure = [0] * len(pattern)
length = 0
for index in range(1, len(pattern)):
# 다음 글자가 이어지지 않으면 더 짧은 경계(border)로 물러난다
while length > 0 and pattern[index] != pattern[length]:
length = failure[length - 1]
if pattern[index] == pattern[length]:
length += 1
failure[index] = length
return failure
def shortest_period(text: str) -> int:
"""text를 반복으로 만드는 가장 짧은 단위의 길이. 딱 나누어떨어지지 않으면 text 길이 자체다."""
if not text:
return 0
period = len(text) - failure_function(text)[-1]
return period if len(text) % period == 0 else len(text)
if __name__ == "__main__":
assert failure_function("ABABAC") == [0, 0, 1, 2, 3, 0]
assert failure_function("ABACABAB") == [0, 0, 1, 0, 1, 2, 3, 2]
assert failure_function("AAAA") == [0, 1, 2, 3]
assert failure_function("ABCD") == [0, 0, 0, 0]
assert failure_function("") == []
assert shortest_period("ABCABCABC") == 3
assert shortest_period("ABCABCAB") == 8
assert shortest_period("AAAA") == 1
print("ok")KMP
"""KMP 탐색: 틀리면 본문 위치는 그대로 두고, 실패 함수가 알려 준 만큼만 패턴을 되돌린다.
시간: O(n + m) — 표 만들기 O(m), 탐색 중 비교는 많아야 2n번
공간: O(m) — 실패 함수 표
"""
def failure_function(pattern: str) -> list[int]:
"""pattern의 실패 함수 표를 돌려준다."""
failure = [0] * len(pattern)
length = 0
for index in range(1, len(pattern)):
while length > 0 and pattern[index] != pattern[length]:
length = failure[length - 1]
if pattern[index] == pattern[length]:
length += 1
failure[index] = length
return failure
def kmp_search(text: str, pattern: str) -> tuple[list[int], int]:
"""pattern이 나오는 시작 위치 목록(겹침 포함)과 글자 비교 횟수를 돌려준다."""
if not pattern:
return [], 0
failure = failure_function(pattern)
matches: list[int] = []
comparisons = 0
matched = 0
for index, char in enumerate(text):
while True:
comparisons += 1
if char == pattern[matched]:
matched += 1
break
if matched == 0:
break
matched = failure[matched - 1]
if matched == len(pattern):
matches.append(index - matched + 1)
# 겹치는 다음 일치를 놓치지 않도록 경계 길이에서 이어 간다
matched = failure[matched - 1]
return matches, comparisons
def naive_matches(text: str, pattern: str) -> list[int]:
"""검산용: 모든 자리를 잘라 비교한다."""
return [
shift
for shift in range(len(text) - len(pattern) + 1)
if text[shift : shift + len(pattern)] == pattern
]
if __name__ == "__main__":
assert kmp_search("ABABAABABAC", "ABABAC") == ([5], 14)
assert kmp_search("AABAACAABAA", "AABA") == ([0, 6], 13)
assert kmp_search("ABABABAB", "ABAB") == ([0, 2, 4], 8)
for text, pattern in [("AAAAAA", "AA"), ("HELLO", "XYZ"), ("ABCABDABCABC", "ABCABC")]:
matches, comparisons = kmp_search(text, pattern)
assert matches == naive_matches(text, pattern)
assert comparisons <= 2 * len(text)
assert kmp_search("AB", "ABC") == ([], 2)
assert kmp_search("", "A") == ([], 0)
print("ok")라빈-카프
"""라빈-카프: 창의 해시를 굴려 O(1)에 갱신하고, 해시가 같을 때만 글자를 비교한다.
시간: 평균 O(n + m), 최악 O(nm) (모든 창이 가짜 일치일 때)
공간: O(1) — 해시 몇 개만 든다
"""
BASE = 256
MODULUS = 1_000_000_007
def rabin_karp(
text: str,
pattern: str,
base: int = BASE,
modulus: int = MODULUS,
) -> tuple[list[int], int]:
"""pattern이 나오는 시작 위치 목록과 가짜 일치(해시만 같은 창) 수를 돌려준다."""
length = len(pattern)
if length == 0 or length > len(text):
return [], 0
# 창에서 나가는 글자의 자릿값 base^(m-1)
high_power = pow(base, length - 1, modulus)
pattern_hash = 0
window_hash = 0
for index in range(length):
pattern_hash = (pattern_hash * base + ord(pattern[index])) % modulus
window_hash = (window_hash * base + ord(text[index])) % modulus
matches: list[int] = []
spurious = 0
for start in range(len(text) - length + 1):
if start > 0:
leaving = ord(text[start - 1])
entering = ord(text[start + length - 1])
window_hash = ((window_hash - leaving * high_power) * base + entering) % modulus
if window_hash != pattern_hash:
continue
# 해시가 같아도 글자가 다를 수 있으니 반드시 확인한다
if text[start : start + length] == pattern:
matches.append(start)
else:
spurious += 1
return matches, spurious
if __name__ == "__main__":
# 숫자 글자를 십진수로 읽는 노트의 예: base 10, 법 13 → 897이 가짜 일치
digits = "535897932384"
as_digits = "".join(chr(int(digit)) for digit in digits)
assert rabin_karp(as_digits, "".join(chr(int(d)) for d in "793"), 10, 13) == ([5], 1)
# 법 11에서는 15, 59, 92가 26과 해시만 같다
pi_digits = "".join(chr(int(digit)) for digit in "31415926535")
assert rabin_karp(pi_digits, chr(2) + chr(6), 10, 11) == ([6], 3)
# 큰 법에서는 가짜 일치가 거의 없다
assert rabin_karp("ABABAABABAC", "ABABAC") == ([5], 0)
assert rabin_karp("AAAAA", "AA") == ([0, 1, 2, 3], 0)
assert rabin_karp("AB", "ABC") == ([], 0)
print("ok")편집 거리
"""편집 거리(레벤슈타인 거리): 넣기·지우기·바꾸기를 각각 1로 칠 때 한 문자열을 다른 문자열로 바꾸는 최소 비용.
시간: O(nm) — (n + 1) × (m + 1)칸을 칸마다 O(1)에 채운다
공간: O(nm) — 편집 순서를 되짚으려고 표를 남긴다(거리만 필요하면 O(min(n, m)))
"""
def edit_distance_table(source: str, target: str) -> list[list[int]]:
"""table[i][j] = source 앞 i글자를 target 앞 j글자로 바꾸는 비용인 표를 돌려준다."""
table = [[0] * (len(target) + 1) for _ in range(len(source) + 1)]
for row in range(len(source) + 1):
table[row][0] = row
for column in range(len(target) + 1):
table[0][column] = column
for row in range(1, len(source) + 1):
for column in range(1, len(target) + 1):
replace_cost = 0 if source[row - 1] == target[column - 1] else 1
table[row][column] = min(
table[row - 1][column] + 1,
table[row][column - 1] + 1,
table[row - 1][column - 1] + replace_cost,
)
return table
def edit_script(source: str, target: str) -> list[str]:
"""표를 오른쪽 아래에서 거꾸로 되짚어 비용이 드는 편집만 앞에서부터 돌려준다."""
table = edit_distance_table(source, target)
row, column = len(source), len(target)
edits: list[str] = []
while row > 0 or column > 0:
here = table[row][column]
if row > 0 and column > 0:
same = source[row - 1] == target[column - 1]
if table[row - 1][column - 1] + (0 if same else 1) == here:
if not same:
edits.append(f"{source[row - 1]}→{target[column - 1]} 바꾸기")
row -= 1
column -= 1
continue
if row > 0 and table[row - 1][column] + 1 == here:
edits.append(f"{source[row - 1]} 지우기")
row -= 1
continue
edits.append(f"{target[column - 1]} 넣기")
column -= 1
return edits[::-1]
if __name__ == "__main__":
assert edit_distance_table("KITTEN", "SITTING")[-1][-1] == 3
assert edit_script("KITTEN", "SITTING") == ["K→S 바꾸기", "E→I 바꾸기", "G 넣기"]
assert edit_distance_table("HORSE", "ROS")[-1][-1] == 3
assert edit_script("CAT", "CART") == ["R 넣기"]
# 레벤슈타인은 맞바꾸기가 없어서 TEH → THE가 2다
assert edit_distance_table("TEH", "THE")[-1][-1] == 2
assert edit_distance_table("TEH", "TEA")[-1][-1] == 1
assert edit_distance_table("", "ABC")[-1][-1] == 3
assert edit_script("SAME", "SAME") == []
print("ok")접미사 배열
"""접미사 배열: 모든 접미사를 사전순으로 정렬한 시작 위치. 패턴은 이진 탐색으로 찾는다.
시간: 만들기 O(n log² n) (앞 1, 2, 4…글자 순위를 두 배씩 늘리며 정렬), 찾기 O(m log n)
공간: O(n) — 정수 배열 몇 개
"""
def suffix_array(text: str) -> list[int]:
"""text의 접미사 배열을 돌려준다(순위 두 배 늘리기)."""
count = len(text)
order = list(range(count))
rank = [ord(char) for char in text]
width = 1
while width < count:
# 앞 2·width글자의 순위 = (앞 width글자 순위, 그다음 width글자 순위). 끝을 넘으면 -1로 가장 앞에 둔다
def key(start: int) -> tuple[int, int]:
second = rank[start + width] if start + width < count else -1
return rank[start], second
order.sort(key=key)
new_rank = [0] * count
for position in range(1, count):
previous, current = order[position - 1], order[position]
new_rank[current] = new_rank[previous] + (key(previous) != key(current))
rank = new_rank
if rank[order[-1]] == count - 1:
break
width *= 2
return order
def lcp_array(text: str, order: list[int]) -> list[int]:
"""정렬된 이웃 접미사끼리의 공통 접두사 길이. 첫 칸은 앞 이웃이 없어 0이다."""
result = [0] * len(order)
for position in range(1, len(order)):
left, right = order[position - 1], order[position]
length = 0
while (
right + length < len(text)
and left + length < len(text)
and text[left + length] == text[right + length]
):
length += 1
result[position] = length
return result
def find_all(text: str, order: list[int], pattern: str) -> list[int]:
"""pattern으로 시작하는 접미사의 순위 구간을 이진 탐색 두 번으로 찾아, 시작 위치를 오름차순으로 돌려준다."""
def prefix_at(position: int) -> str:
start = order[position]
return text[start : start + len(pattern)]
low, high = 0, len(order)
while low < high:
middle = (low + high) // 2
if prefix_at(middle) < pattern:
low = middle + 1
else:
high = middle
first = low
high = len(order)
while low < high:
middle = (low + high) // 2
if prefix_at(middle) <= pattern:
low = middle + 1
else:
high = middle
return sorted(order[first:low])
def distinct_substrings(text: str) -> int:
"""서로 다른 (빈 문자열이 아닌) 부분 문자열의 수 = n(n + 1)/2 − LCP 합."""
order = suffix_array(text)
count = len(text)
return count * (count + 1) // 2 - sum(lcp_array(text, order))
if __name__ == "__main__":
banana = suffix_array("banana")
assert banana == [5, 3, 1, 0, 4, 2]
assert lcp_array("banana", banana) == [0, 1, 3, 0, 0, 2]
assert find_all("banana", banana, "ana") == [1, 3]
assert find_all("banana", banana, "na") == [2, 4]
assert find_all("banana", banana, "x") == []
papaya = suffix_array("papaya")
assert papaya == [5, 1, 3, 0, 2, 4]
assert find_all("papaya", papaya, "pa") == [0, 2]
assert distinct_substrings("mamama") == 11
# 단순 정렬과 같은 결과
for text in ["mississippi", "aaaa", "abcab", "a"]:
expected = sorted(range(len(text)), key=lambda start: text[start:])
assert suffix_array(text) == expected
assert suffix_array("") == []
print("ok")