[자료구조] Text pattern matching- Naive Approach 방법, 코드 구현

Naive Approach는 텍스트 패턴 매칭 알고리즘 중 가장 기본적이고 직관적인 방법이다. 이 방법은 단순히 텍스트 내에서 패턴을 찾기 위해 모든 가능한 위치에서 패턴을 하나씩 비교하는 방식으로 동작한다. Naive Approach는 다음과 같은 단계로 구성된다:

1. 텍스트와 패턴 길이 확인: 텍스트 T의 길이를 n, 패턴 P의 길이를 m이라고 할 때, 가능한 모든 시작 위치를 검사하기 위해 T의 길이에서 P의 길이를 뺀 만큼의 위치까지 반복을 수행한다.
2. 모든 시작 위치 검사: 텍스트의 각 가능한 시작 위치에서 패턴과의 일치를 검사한다. 이를 위해 T의 위치 i부터 i + m - 1까지의 부분 문자열을 패턴 P와 비교한다.
3. 패턴 일치 확인: 패턴의 모든 문자가 일치하는지 확인하고, 일치하면 그 시작 위치를 기록하거나 출력한다.

 

[관련 코드] - python

 

def naive_pattern_matching(T, P):
    n = len(T)
    m = len(P)
    
    # 결과를 저장할 리스트
    result = []
    
    # 가능한 모든 시작 위치를 확인
    for i in range(n - m + 1):
        # 패턴 P가 텍스트 T의 현재 위치 i에서 일치하는지 확인
        match = True
        for j in range(m):
            if T[i + j] != P[j]:
                match = False
                break
        
        # 일치하는 경우 결과에 추가
        if match:
            result.append(i)
    
    return result

# 예시 사용
text = "AABAACAADAABAAABAA"
pattern = "AABA"
matches = naive_pattern_matching(text, pattern)
print("패턴이 일치하는 위치:", matches)