실습

 

Naive Matching

 

 

 

def naive_matching(text, pattern):
    n = len(text)
    m = len(pattern)
    
    comparison_count = 0
    match_count = 0
    
    # i는 텍스트에서 시작 위치 (0-indexed)
    for i in range(n - m + 1):
        # 현재 위치에서 패턴과 매칭 시도
        is_match = True
        for j in range(m):
            comparison_count += 1  # 비교 횟수 증가
            if text[i + j] != pattern[j]:
                is_match = False
                break  # 불일치 발견 시 즉시 중단
        
        if is_match:
            match_count += 1
    
    return comparison_count, match_count

# 입력 받기
text = input().strip()
pattern = input().strip()

# Naive 매칭 실행
comparisons, matches = naive_matching(text, pattern)

# 결과 출력
print(comparisons, matches)

 

 

Basic Rabin-Karp

 

 

import sys

def solve():
    # 입력을 읽어옵니다. (공백과 줄바꿈 모두 처리)
    input_data = sys.stdin.read().split()
    
    # 입력이 부족한 경우 예외 처리
    if len(input_data) < 2:
        return

    text = input_data[0]
    pattern = input_data[1]

    n = len(text)
    m = len(pattern)
    
    # 예외 처리: 패턴이 본문보다 긴 경우
    if m > n:
        print(0)
        return

    # 문자 매핑 함수 (a=0, b=1, ... j=9)
    def to_int(char):
        return ord(char) - ord('a')

    d = 10
    p = 0
    a = 0
    
    # 가장 높은 자릿수의 가중치 계산 (d^(m-1))
    h = d ** (m - 1)

    # 1. 초기 해시값 계산 (첫 번째 윈도우 & 패턴)
    for i in range(m):
        p = d * p + to_int(pattern[i])
        a = d * a + to_int(text[i])

    match_count = 0
    results = []

    # 2. 루프 실행 (1 부터 n-m+1 까지)
    # 파이썬 range는 0부터 시작하므로 0 ~ n-m 로 매핑됩니다.
    for i in range(n - m + 1):
        # (1) 위치에서 a 출력
        # 주의: 업데이트 전의 값을 먼저 출력합니다.
        results.append(str(a))
        
        # if(i != 1) 조건에 해당 (파이썬에서는 i != 0)
        # 이전 윈도우의 값을 바탕으로 현재 윈도우의 해시값 업데이트
        if i != 0:
            # 제거될 문자: text[i-1]
            # 추가될 문자: text[i+m-1]
            prev_char = to_int(text[i-1])
            next_char = to_int(text[i+m-1])
            
            # 롤링 해시 공식: d * (이전값 - 제거문자*h) + 추가문자
            a = d * (a - prev_char * h) + next_char

        # 매칭 확인
        if p == a:
            match_count += 1
            
    # 결과 출력 (숫자 사이 공백, 마지막에 개수)
    print(" ".join(results) + " " + str(match_count))

if __name__ == "__main__":
    solve()

 

 

 

Rabin-Karp

 

 

import sys

# 문제에서 정의한 mod 함수 구현
def custom_mod(x, y):
    return ((x % y) + y) % y

def to_int(char):
    return ord(char) - ord('a')

def solve():
    # 입력 받기
    input_data = sys.stdin.read().split()
    
    # 입력 유효성 검사
    if len(input_data) < 2:
        return

    text = input_data[0]
    pattern = input_data[1]

    n = len(text)
    m = len(pattern)

    # 패턴이 본문보다 긴 경우 처리
    if m > n:
        print("0") # 혹은 아무것도 출력하지 않거나 상황에 맞춰 처리
        return

    # 상수 설정
    d = 26
    q = 113

    # 초기 해시값 계산
    p = 0 # 패턴의 해시
    b = 0 # 본문 첫 윈도우의 해시
    
    for i in range(m):
        p = custom_mod(d * p + to_int(pattern[i]), q)
        b = custom_mod(d * b + to_int(text[i]), q)

    # d^(m-1) mod q 미리 계산
    h = 1
    for _ in range(m - 1):
        h = custom_mod(h * d, q)

    results = []
    match_count = 0

    # 메인 루프 (0 부터 n-m 까지)
    for i in range(n - m + 1):
        # (1) 위치에서 b 출력 (현재 해시값 기록)
        results.append(str(b))

        # 첫 번째 루프가 아니면 롤링 해시 업데이트
        # 주의: 문제의 pseudo-code 흐름상, '현재 윈도우 검사' 전에 '이전 값을 출력'하고 
        # '업데이트' 하는 로직이 섞여 있어, i=0일 때는 업데이트를 건너뜁니다.
        if i != 0:
            prev_char = to_int(text[i-1])
            next_char = to_int(text[i+m-1])
            
            # b_i = (d * (b_{i-1} - h * A[i-1]) + A[i+m-1]) mod q
            # 식을 단계별로 나누어 mod 적용
            temp = custom_mod(b - custom_mod(h * prev_char, q), q)
            b = custom_mod(d * temp + next_char, q)

        # 해시값 비교 및 문자열 실제 비교
        if p == b:
            # 해시 충돌 가능성이 있으므로 실제 문자열이 같은지 확인
            if text[i : i+m] == pattern:
                match_count += 1

    # 결과 출력
    print(" ".join(results) + " " + str(match_count))

if __name__ == "__main__":
    solve()

 

 

KMP

 

 

import sys

def solve():
    # 입력을 읽어옵니다.
    input_data = sys.stdin.read().splitlines()
    
    # 입력 데이터 유효성 확인
    if len(input_data) < 2:
        return

    # 첫 줄: 검색할 문장 (Text)
    # 둘째 줄: 찾고자 하는 패턴 (Pattern)
    text_origin = input_data[0].strip()
    pattern_origin = input_data[1].strip()

    n = len(text_origin)
    m = len(pattern_origin)

    # 1-based Indexing 구현을 위해 앞에 더미 문자 추가
    A = " " + text_origin
    P = " " + pattern_origin

    # 1. 전처리 (Preprocessing): pi 테이블 생성
    # pi[j]: j번 인덱스에서 매칭 실패 시 이동할 패턴의 인덱스
    # 표준 LPS(Longest Prefix Suffix) 배열을 구한 뒤 문제의 pi 형식으로 변환합니다.
    
    # 표준 LPS 계산 (0-based 기준 pattern_origin 사용)
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern_origin[i] == pattern_origin[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    
    # 문제의 로직(j <- pi[j])에 맞는 pi 배열 생성 (크기 m+2)
    # 매칭 실패 시 돌아갈 위치는 (직전까지 일치한 길이 + 1)이 됩니다.
    pi = [0] * (m + 2)
    pi[1] = 0 # j=1에서 실패하면 0으로 가서 i를 증가시킴
    
    for k in range(2, m + 2):
        # k 위치에서의 pi값은 (k-1) 길이까지의 부분문자열의 LPS 길이 + 1
        # lps 배열 인덱스는 k-2에 해당
        pi[k] = lps[k-2] + 1

    # 2. KMP 알고리즘 수행 (유사코드 로직 준수)
    i = 1 # 본문 포인터
    j = 1 # 패턴 포인터
    cnt = 0 # 비교 횟수
    found_any = False # 매칭 성공 여부

    while i <= n:
        cnt += 1 # while문 진입할 때마다 카운트 증가
        
        # j==0 이거나 문자가 일치하면 전진
        if j == 0 or A[i] == P[j]:
            i += 1
            j += 1
        else:
            # 불일치 시 pi 테이블을 이용해 j 이동
            j = pi[j]

        # 패턴을 모두 찾은 경우 (j가 m+1에 도달)
        if j == m + 1:
            print(cnt) # 현재 비교 횟수 출력
            found_any = True
            j = pi[j] # 다음 매칭을 위해 j 위치 재조정

    if not found_any:
        print("fail")

if __name__ == "__main__":
    solve()

 

 

 

Boyer-Moore

 

import sys

def solve():
    # 입력을 읽어옵니다.
    input_data = sys.stdin.read().split()
    
    if len(input_data) < 2:
        return

    text = input_data[0]
    pattern = input_data[1]

    n = len(text)
    m = len(pattern)

    # 예외 처리: 패턴이 본문보다 긴 경우
    if m > n:
        print("0 0")
        return

    # 1. Jump 테이블 계산 (computeJump)
    # 모든 가능한 문자에 대해 기본 이동 거리는 패턴의 길이(m)로 설정
    # 입력이 알파벳 소문자라고 가정하면 딕셔너리를 사용하여 유연하게 처리 가능
    jump = {}
    
    # 패턴의 0번째부터 m-2번째 문자까지에 대해 이동 거리 계산
    # 마지막 문자(m-1)는 테이블 계산에서 제외 (단, 앞에 같은 문자가 있으면 그 값 유지)
    for k in range(m - 1):
        jump[pattern[k]] = m - 1 - k

    # 2. Boyer-Moore-Horspool 검색 수행
    i = 0
    cnt = 0        # (1) 위치에서의 카운트
    match_count = 0 # 발견된 패턴 개수

    while i <= n - m:
        j = m - 1
        k = i + m - 1
        
        # 뒤에서부터 앞으로 문자 비교
        # 유사코드: while(j > 0 and P[j] == A[k])
        # 파이썬(0-based): j가 0보다 크거나 같아야 함
        while j >= 0 and pattern[j] == text[k]:
            # (1) 여기서 카운팅 한다.
            # 루프 조건(문자 일치)을 만족해야만 이곳에 도달함
            cnt += 1
            j -= 1
            k -= 1
        
        # j가 -1이 되면 모든 문자가 일치했다는 의미
        if j == -1:
            match_count += 1
        
        # 이동 (Shift)
        # i = i + jump[A[i+m-1]]
        # 텍스트 윈도우의 가장 오른쪽 문자(last_char)를 기준으로 점프
        last_char = text[i + m - 1]
        
        # jump 테이블에 없는 문자는 m만큼 이동
        shift = jump.get(last_char, m)
        i += shift

    # 결과 출력
    print(f"{cnt} {match_count}")

if __name__ == "__main__":
    solve()