[수업기록] 알고리즘 : string(2)

240805 파이썬반

 

1.패턴 매칭에 사용되는 알고리즘들

 

1) 고지식한 패턴 검색 알고리즘(Brute Force)

: 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내 문자들을 일일이 비교하는 방식(==모든 경우의 수 다 따짐)

: ex. 비밀번호 4자리를 푸는 문제(0000~9999)

: 최악의 경우 시간 복잡도는 텍스트 모든 위치에서 패턴을 비교해야하기에 O(M*N)이 됨

: 길이가 10000인 문자열에서 길이 80인 패턴 찾는다하면, 10000*80 = 800000번의 비교

p = 'TTA' #찾을패턴
t = "TTTTTABC" #전체 텍스트
N =len(t) # 전체 텍스트의 길이
M = len(p) #찾을 패턴의 길이

for i in range(N-M+1): #비교 시작위치
	for j in range(M):
    	if t[i+j] != p[j]: 🤔
        	break # for j, 다음글자부터 비교 시작 
            
    else:
    	cnt += 1

def b(t,p):
    N = len(t)
    M = len(p)
    for i in range(N-M+1):
        for j in range(M):
            if t[i+j] != p[j]:
                break
        else:
            return i  #패턴을 찾은 경우
    return -1

 

2) KMP 알고리즘 : 대표적 문자열 매칭 알고리즘

:  불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고있으므로, 불일치가 발생한 앞 부분에 대해 다시 비교하지 않고 매칭 수행

: 시간 복잡도O(M+N)

def compute_lps(pattern):
    """
    KMP 알고리즘에서 사용할 부분 일치 테이블(LPS: Longest Prefix Suffix) 생성

    Args:
        pattern (str): LPS 배열을 계산할 패턴 문자열

    Returns:
        list: 계산된 LPS 배열

    LPS 배열은 각 인덱스에서 끝나는 부분 문자열의 가장 긴 접두사이면서 접미사인 부분의 길이를 저장.
    이 배열은 KMP 알고리즘에서 불필요한 비교를 줄이는 데 사용.
    """
    lps = [0] * len(pattern)
    length = 0  # 이전까지 일치한 접두사-접미사의 길이
    i = 1  # 패턴의 두 번째 문자부터 시작 (첫 번째 문자의 LPS는 항상 0이므로)

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            # 현재 문자가 이전까지 일치한 접두사의 다음 문자와 같으면
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                # 불일치 시, 이전 일치 길이를 활용하여 길이 조정
                length = lps[length - 1]
            else:
                # 일치하는 접두사가 없으면 0으로 설정
                lps[i] = 0
                i += 1

    return lps


def kmp_search(text, pattern):
    """
    KMP(Knuth-Morris-Pratt) 알고리즘을 사용하여 텍스트에서 패턴을 검색

    Args:
        text (str): 검색할 대상 문자열
        pattern (str): 찾고자 하는 패턴 문자열

    Returns:
        list: 패턴이 발견된 텍스트 내의 모든 시작 위치(인덱스)

    KMP 알고리즘은 패턴의 접두사와 접미사 정보를 이용하여 불필요한 비교를 줄이고,
    효율적으로 문자열 검색을 수행합니다. 시간 복잡도는 O(N+M)
    여기서 N은 텍스트의 길이, M은 패턴의 길이
    """
    N = len(text)
    M = len(pattern)
    lps = compute_lps(pattern)  # LPS 배열 계산

    i = 0  # 텍스트 인덱스
    j = 0  # 패턴 인덱스
    results = []  # 패턴이 발견된 위치를 저장할 리스트

    while i < N:
        if pattern[j] == text[i]:
            # 문자가 일치하면 양쪽 인덱스를 증가
            i += 1
            j += 1

        if j == M:
            # 패턴을 찾은 경우
            results.append(i - j)  # 패턴의 시작 위치 저장
            j = lps[j - 1]  # 다음 일치를 위해 j 조정
        elif i < N and pattern[j] != text[i]:
            # 불일치가 발생한 경우
            if j != 0:
                # j를 LPS 배열을 이용하여 조정
                j = lps[j - 1]
            else:
                # 패턴의 첫 문자부터 불일치면 텍스트 인덱스만 증가
                i += 1

    return results
# 예시 사용

# PATTERN = "AAAAAA"
# print(compute_lps(PATTERN)) 
# #A A A A A A
# #0 1 2 3 4 5

# PATTERN = "ABABABAB"
# print(compute_lps(PATTERN)) 
# #A B A B A B A B
# #0 0 1 2 3 4 5 6

# PATTERN = "ABCABCABC"
# print(compute_lps(PATTERN)) 
# #A B C A B C A B C
# #0 0 0 1 2 3 4 5 6

PATTERN = "ABABCABAB"
print(compute_lps(PATTERN)) 
#A B A B C A B A B
#0 0 1 2 0 1 2 3 4


TEXT = "ABABDABACDABABCABAB"

matches = kmp_search(TEXT, PATTERN)
print(f"패턴이 발견된 위치: {matches}") #패턴이 발견된 위치: [10]

 

3) 보이어-무어 알고리즘 

: 패턴의 맨끝(오른쪽)부터 먼저 비교 -> n개씩 한꺼번에 건너뛰기

: 패턴에 오른쪽 끝에 있는 문자가 불일치 하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동 거리는 무려 패턴의 길이만큼 된다

: 최악의 경우 수행시간 O(M*N)

: 입력에 따라 다르지만 일반적으로 O(N)보다 시간이 덜 든다

def boyer_moore_search(text, pattern):
    """
    보이어-무어 문자열 검색 알고리즘을 구현한 함수.

    이 함수는 주어진 텍스트에서 패턴을 검색하고, 패턴이 발견된 모든 위치를 출력
    보이어-무어 알고리즘은 패턴의 끝에서부터 비교를 시작하며, 
    불일치가 발생했을 때 효율적으로 이동하는 특징이 있어 평균적으로 빠른 검색 속도

    시간 복잡도:
    - 최선의 경우: O(N/M)  # 여기서 N은 텍스트 길이, M은 패턴 길이
    - 평균의 경우: O(N)
    - 최악의 경우: O(NM)

    매개변수:
    text (str): 검색할 대상 문자열
    pattern (str): 찾고자 하는 패턴 문자열

    반환값:
    없음. 패턴이 발견된 위치를 직접 출력

    """
    # 패턴의 길이
    M = len(pattern)
    # 텍스트의 길이
    N = len(text)
    
    # 나쁜 문자 휴리스틱 테이블 생성
    # 이 테이블은 패턴의 각 문자가 마지막으로 나타나는 위치를 저장
    bad_char = {}
    for i in range(M):
        bad_char[pattern[i]] = i

    # 검색 시작
    i = 0
    while i <= N - M:
        j = M - 1

        # 패턴의 끝에서부터 비교 시작
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1

        # 패턴을 찾은 경우
        if j < 0:
            print(f"패턴을 찾았습니다. 인덱스: {i}")
            # 다음 위치로 이동
            i += (M - bad_char.get(text[i + M], -1) if i + M < N else 1)
        else:
            # 불일치가 발생한 경우, 나쁜 문자 휴리스틱을 사용하여 이동
            i += max(1, j - bad_char.get(text[i + j], -1))

# 테스트
text = "ABAAABCD"
pattern = "ABC"
boyer_moore_search(text, pattern)

 

4) 예제

회문(level과 같이 거꾸로 읽어도 제대로 읽은 것과 같은 문장이나, 낱말) 찾기

- 단어를 입력받아 회문이면 1을, 아니라면 0을 출력 

# level # 1
# samsung # 0
# eye # 1
# 낱말이나 문장 길이가 짝수이던 홀수이던 (홀수면 가운데 꺼 고려x) -> 비교횟수 i는 0부터 N//2-1

s = input()
N = len(s)
answer = 1
for i in range(N//2):
    if s[i] != s[N-1-i]:
        answer = 0 🤔
        break
print(answer)

 

잠깐, 회문 풀기 전 리스트 복습 한번 더 가자. 

numList = [1,2,3,4,5]
#N=5       0,1 2 3 4

#거꾸로 리스트 순회
#N-1 -> 0
for i in range(n-1, -1, -1) :
    print(numList[i])
    
for i in range(N) : #뒤집기
    print(numList[N-1-i])