[알고리즘] 패턴 매칭 알고리즘 소스코드

- 한번만 찾는 경우 

# 패턴이 있을 수 있는 가능한 시작 위치
for i in range(n-m+1):
    # 패턴의 길이 만큼 비교
    for j in range(m):
        # 일치하지 않으면 다음으로 넘어감
        if p[j] != t[i+j]:
            break
    else:
        # 매칭 성공
        break

 

- 모든 패턴을 찾을 때 : 방법1

 

i = 0
while i <= n-m:
    for j in range(m):
        if p[j] != t[i+j]:
            break
    else:
        # 매칭 성공
        i += m - 1
i += 1

• 개인적으로 직관적

 

- 모든 패턴을 찾을 때 : 방법2

i = j = 0
while i < n:
    if p[j] != t[i]:
        i = i-j
        j = -1

    i, j = i+1, j+1
    if j == m:
        print(i-m, t[i-m:i])
        j = 0