[Python] [알고리즘] 2. String

Brute-Force

본문 문자열을 처음부터 끝까지 차례대로 순회하며 패턴 내 문자들을 하나하나 비교하는 방식으로 동작한다.

p = 'is' #찾을 패턴
t = 'This is a book' #전체 텍스트
M = len(p)
N = len(t)

def BruteForce(p,t):
	i = 0 #t의 idx
	j = 0 #p의 idx
	while j<M and i<N:
		if t[i] != p[j]:
			i -= j
			j = -1
		i = i + 1
		j = j+1
	if j == M :return i-M #검색 성공
	else: return -1

p ='ab'
t ='aaaaaabaaaababb'
M = len(p)
N = len(t)

def bf(p, t):
    i = 0#t에서의 비교 위치
j = 0# p에서의 비교 위치

while i < N and j < M:#비교할 문장이 남아있고 패턴 찾기 전에만 while문 돌기
if t[i] != p[j]:#서로 다른 문자를 만나면
	i -= j#비교를 시작한 위치로
	j = -1#패턴의 시작 전으로
	i += 1
    	j += 1
    if j == M:#패턴을 찾은 경우
return i-M
    else:
        return -1

print(bf(p,t))

T = "This pattern matching algorithm"

def brute(P):
    lenP = len(P)
    lenT = len(T)
    idx_T = 0
    for idx_T in range(lenT-lenP+1):
        idxP = 0
        while idxP < lenP and T[idx_T+idxP] == P[idxP]:
            idxP += 1
        if idxP == lenP:
            return idx_T
    return -1

print(brute('patt'))

KMP 알고리즘(O: M+N)

불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대해 다시 비교하지 않고 매칭을 수행한다. 패턴을 전처리하여 배열 next[M}을 구해서 잘못된 시작을 최소화한다.(next[M]은 불일치가 발생했을 경우 이동할 다음 위치) 매칭이 실패했을 경우 돌아갈 곳을 생각한다.

보이어-무어 알고리즘(O: M*N)

오른쪽에서 왼쪽으로 비교하는 알고리즘. 대부분의 상용 SW에서 채용한다. 패턴의 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 안에 존재하지 않는 경우, 패턴의 길이 만큼 건너뛴 후 뒤에서부터 비교하는 알고리즘이다.

오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하는 경우는 패턴에서 일치하는 문자를 찾아 이동한다.

for문은 하나씩 이동하는 방법이기 때문에 보이어-무어 알고리즘은 while문을 사용하여야 한다. O의 경우 크지만, 일반적으로 (n)보다 시간이 덜 든다.