All
스트링 알고리즘
문자열(String)에 대한 다양한 문제를 해결하기 위한 알고리즘들의 총칭
•
문자열 내부 구조를 분석하거나 특정 패턴을 찾는 데 사용됨
•
주로 문자열 처리의 효율성을 높이기 위한 알고리즘들을 포함
대표적인 문제 유형
•
문자열 매칭
•
문자열 압축
•
최장 공통 부분 수열 LCS
•
최장 반복 부분 문자열 LPS
•
회문 여부 판별 (Palindrome Detection)
•
사전 순 비교 등등
문자열 매칭
텍스트 내에서 주어진 패턴이 어디에 존재하는지를 찾는 문제
•
입력 문자열 (텍스트) T: t₀ t₁ t₂ … tₙ₋₁ (길이 n)
•
패턴 문자열 P: p₀ p₁ p₂ … pₘ₋₁ (길이 m)
•
조건: n ≥ m
→ 문제: 텍스트 T 안에서 패턴 P가 일치하는 시작 위치를 모두 찾아라
브루트-포스
•
텍스트의 각 위치부터 시작해 패턴의 각 문자와 일일이 비교하여 전부 일치하는지 확인
예시
텍스트 T: a a b a a b a a a
패턴 P: a a b a a
•
위치 0일때 → 일치:
◦
T = a a b a a
◦
P = a a b a a
•
위치 1일때 → 불일치:
◦
T = a b a a b
◦
P = a a b a a
구현
def brute_force_match(T, P):
n, m = len(T), len(P)
for i in range(n - m + 1):
match = True
for j in range(m):
if T[i + j] != P[j]:
match = False
break
if match:
print(f"Pattern found at index {i}")
Python
복사
문자열 매칭의 고급 기법
보다 효율적인 탐색을 위해 텍스트나 패턴을 전처리하여 불필요한 비교를 줄이는 방식 사용
•
패턴 기반 전처리
◦
라빈-카프 알고리즘
◦
KMP 알고리즘
◦
보이어-무어 알고리즘
•
텍스트 기반 전처리
◦
접미사 트리 (Suffix Tree)
◦
접미사 배열 (Suffix Array)
→ 이번 시간에는 이 중 라빈-카프와 KMP 알고리즘을 중심으로 학습
라빈-카프 Rabin-Karp 알고리즘
문자열을 정수 해시값으로 바꿔서 비교하는 방식
모든 위치에서 문자를 하나씩 비교하는 대신, 해시값이 같은 경우에만 실제 문자를 비교
핵심 아이디어
•
문자열을 숫자로 바꾸는 해시 함수를 사용해, 텍스트와 패턴을 빠르게 비교
•
패턴과 길이가 같은 구간의 해시값이 일치하면 후보로 간주해 비교 수행
해시 함수 예시
•
문자에 숫자 값을 매기고, 이를 진법 형태로 계산
•
예: a=0, b=1, c=2, ..., z=25
•
예: 문자열 aabaa를 26진수처럼 해싱
•
여기서 mod 101은 충돌 방지를 위한 소수 modulo
슬라이딩 윈도우 방식
•
처음 위치(0번 위치)는 전체 해시 계산이 필요 → O(m)
•
이후 위치부터는 이전 해시값을 이용해 O(1)으로 갱신 가능
예시
텍스트 T = a a b a a b a a a
패턴 P = a a b a a
패턴 해시: 70 (예시 기준)
위치 | 부분 문자열 | 해시값 | 일치 여부 |
0 | a a b a a | 70 | 후보 → 문자 비교 |
1 | a b a a b | 3 | 불일치 |
2 | b a a b a | 78 | 불일치 |
3 | a a b a a | 70 | 후보 → 문자 비교 |
구현
def rabin_karp(T, P, d=256, q=101):
n, m = len(T), len(P)
h = pow(d, m-1, q) # d^(m-1) % q
p_hash, t_hash = 0, 0
# 초기 해시 계산
for i in range(m):
p_hash = (d * p_hash + ord(P[i])) % q
t_hash = (d * t_hash + ord(T[i])) % q
for i in range(n - m + 1):
# 해시가 같으면 실제 문자열 비교
if p_hash == t_hash:
if T[i:i+m] == P:
print(f"Pattern found at index {i}")
# 다음 해시 계산 (슬라이딩 윈도우)
if i < n - m:
t_hash = (d * (t_hash - ord(T[i]) * h) + ord(T[i + m])) % q
if t_hash < 0:
t_hash += q
Python
복사
성능
•
시간복잡도:
◦
해시값 계산: O(n)
◦
패턴 해시 계산: O(m)
◦
실제 매치 확인: O(km) (k는 해시가 같아 실제 비교하는 횟수)
•
매치 개수가 상수(해시 충돌 없음): O(n)
•
모든 위치에서 매치(해시 충돌): O(nm)
KMP Knuth-Morris-Pratt 알고리즘
패턴 내부 구조(접두사와 접미사 관계)를 이용하여 중복된 비교를 줄이고 빠르게 문자열을 탐색
핵심 아이디어
•
텍스트에서 패턴이 일치하지 않았을 때, 이전까지 일치한 부분을 버리지 않고 재활용
•
이를 위해 패턴의 접두사(prefix)와 접미사(suffix)가 얼마나 일치하는지를 미리 계산해두는 배열 F(= failure function 또는 pi 배열)를 사용
F배열이란?
•
패턴의 각 위치까지에서 prefix == suffix 되는 최대 길이를 저장한 배열
◦
F[i]는 P[0..i]까지의 부분 문자열에서, 가장 긴 접두사 == 접미사 의 길이 - 1
◦
만약 그런 게 없다면 F[i] = -1
예시 1번
i: 0 1 2 3 4
P: a a b a a
F: -1 0 -1 0 1
•
F[1] = 0: a (접두사) == a (접미사)
•
F[2] = -1: 접두사/접미사 일치 없음
•
F[4] = 1: aa (접두사) == aa (접미사)
예시 2번
T = A T A T A T G A T A T G A A
P = A T A T G A T
F = -1 -1 0 1 -1 0 1
1.
i = 0 (P[0] = 'a')
•
P[0..0] = "a"
•
proper prefix 집합 = {""}, proper suffix 집합 = {""}
•
최장 일치 = "" (길이 0) ⇒ F[0] = 0−1 = −1
2.
i = 1 (P[0..1] = "aa")
•
proper prefixes = {"", "a"}
•
proper suffixes = {"", "a"}
•
최장 일치 = "a" (길이 1) ⇒ F[1] = 1−1 = 0
3.
i = 2 ("aab")
•
proper prefixes = {"", "a", "aa"}
•
proper suffixes = {"", "b", "ab"}
•
공통된 긴 문자열 = "" (길이 0) ⇒ F[2] = 0−1 = −1
4.
i = 3 ("aaba")
•
proper prefixes = {"", "a", "aa", "aab"}
•
proper suffixes = {"", "a", "ba", "aba"}
•
최장 일치 = "a" (길이 1) ⇒ F[3] = 1−1 = 0
5.
i = 4 ("aabaa")
•
proper prefixes = {"", "a", "aa", "aab", "aaba"}
•
proper suffixes = {"", "a", "aa", "baa", "abaa"}
•
최장 일치 = "aa" (길이 2) ⇒ F[4] = 2−1 = 1
알고리즘의 기본 흐름
1.
텍스트 T 에서 인덱스 i = 0부터, 패턴 P 에서 인덱스 j = 0부터 시작
2.
일치(T[i] == P[j])하면 둘 다 i++, j++
3.
j == |P| (패턴 끝까지 다 일치) → 매칭 성공!
4.
불일치(T[i] != P[j])하면
•
만약 j == 0 → 그냥 i++ (패턴 맨 앞부터 다시 비교)
•
j > 0 → j = F[j-1] + 1 (F[j-1]이 “j-1까지의 최장 접두사 길이 −1” 이었으니, +1 하면 “접두사 길이”가 됨)
구현
def KMP_search(T, P):
n, m = len(T), len(P)
F = compute_failure_function(P)
j = -1 # 패턴 포인터
for i in range(n): # 텍스트 포인터
while j >= 0 and T[i] != P[j + 1]:
j = F[j] # 실패 함수 이용해서 점프
if T[i] == P[j + 1]:
j += 1
if j == m - 1:
print(f"Pattern found at index {i - m + 1}")
j = F[j] # 다음 매칭을 위해 점프
Python
복사
성능
•
F배열 생성: O(m)
◦
포인터 j는(idx) 최대 m-1 증가
◦
while 문은 최대 m-1만큼 수행
•
탐색(텍스트 비교): O(n)
◦
j값은 최대 n 증가
•
전체 시간복잡도: O(n)