[문자열] 16916 부분 문자열

부분 문자열

링크 - https://www.acmicpc.net/problem/16916

코드

#16916 부분 문자열 22-02-25
def get_pi(P):
    m = len(P)
    pi = [0 for i in range(m)]
    idx=0
    for i in range(1,m):
        while idx>0 and P[i]!=P[idx]:
            idx=pi[idx-1]
        if P[i]==P[idx]:
            idx+=1
            pi[i]=idx
    return pi
def kmp(S,P):
    n = len(S)
    m = len(P)
    pi = get_pi(P)
    idx =0
    for i in range(n):
        while idx>0 and S[i]!=P[idx]:
            idx=pi[idx-1]
        if S[i]==P[idx]:
            if idx==m-1:
                return 1
            else:
                idx+=1
    return 0
if __name__=='__main__':
    S = input().strip()
    P = input().strip()
    print(kmp(S,P))

풀이 방법

브루트포스 알고리즘으로 풀게 되면 시간초과 문제가 생겼다.
검색을 한 결과 문자열 탐색 알고리즘 중 kmp 알고리즘을 사용해야 한다는 것을 알게 되었다.

kmp 알고리즘을 사용하면 문자열에서 부분 패턴을 찾아내어 문자열 탐색을 하기 때문에 한 칸씩 이동하는 브루트 포스 알고리즘보다 시간을 절약할 수 있다고 이해했다.

참고한 링크 -https://pearlluck.tistory.com/581