1213. [S/W 문제해결 기본] 3일차 - String

출처 : 링크텍스트

1. 풀이 방법

간단하게 사용자 정의 함수를 만들었다. 찾고자하는 단어와 전체 문장을 매개변수로 받아 brute-force 패턴 매칭 알고리즘을 구현하였다.

2. 코드

def bruteforce(p, t):
    M = len(p)
    N = len(t)
    result = 0
    for i in range(N - M + 1):
        t_f = False
        if t[i] == p[0]:
            t_f = True
            for j in range(M):
                if t[i + j] != p[j]:
                    t_f = False
                    break
        if t_f:
            result += 1
    return result

for tc in range(10):
    T = int(input())
    word = input()
    sentence = (input())
    cnt = bruteforce(word, sentence)
    print('#{0} {1}'.format(T, cnt))

3. 개선 사항

위의 방법은 소요시간이 매우 길어질 수 있는 여지가 있으므로 KMP, Boyer-Moore알고리즘을 사용해 시간을 줄이는 방법을 고려해 볼만 하다.