[SWEA] 3143_가장 빠른 문자열 타이핑

📕 문제

어떤 문자열 A를 타이핑하려고 한다.
그냥 한 글자씩 타이핑 한다면 A의 길이만큼 키를 눌러야 할 것이다.
여기에 속도를 조금 더 높이기 위해 어떤 문자열 B가 저장되어 있어서 키를 한번 누른 것으로 B전체를 타이핑 할 수 있다. 이미 타이핑 한 문자를 지우는 것은 불가능하다.

예를 들어 A=”asakusa”, B=”sa”일 때, 다음 그림과 같이 B를 두 번 사용하면 5번 만에 A를 타이핑 할 수 있다.
 

A와 B가 주어질 때 A 전체를 타이핑 하기 위해 키를 눌러야 하는 횟수의 최솟값을 구하여라.

 

# 보이어 무어 알고리즘 이용

def find(pattern, char): # 얼마나 움직일지 결정하는 함수
    for i in range(len(pattern) - 2, -1, -1):
        # 마지막글자와 패턴중 일치하는 숫자가 있다면 그만큼 이동한다.
        if pattern[i] == char:
            return len(pattern) - i - 1
    # 일치하는 글자가 없다면 패턴의 길이만큼 이동한다.
    return len(pattern)

def boyer_moore(pattern, text):
    M = len(pattern)
    N = len(text)
    cnt = N
    i = 0
    # 반복은 최대 긴텍스트 길이 - 작은텍스트 길이
    while i <= N - M:
        j = M - 1

        while j >= 0:
            if pattern[j] != text[i + j]:
                move = find(pattern, text[i + M - 1])
                break
            j = j - 1

        if j == -1:  # 인덱스가 -1이라는 뜻은 모든 글자가 맞았다는 뜻
            cnt -= (M - 1)# 검색 성공
            i += M
        else:  # - 1이 아니라면 글자를 못찾은 것이므로 find에서 넘겨준 값만큼 옆으로 이동
            i += move
    return cnt

T = int(input())
for tc in range(T):
    text, pattern = input().split()
    print('#{0} {1}'.format(tc+1, boyer_moore(pattern, text)))

 

# 정말 간단한 법... ㅎ

T = int(input())
for tc in range(T):
    text, pattern = input().split()
    cnt = text.count(pattern)
    print('#{0} {1}'.format(tc + 1, len(text) - (len(pattern)-1)*cnt))