[백준] 부분 문자열 with python(KMP 알고리즘)

KMP 알고리즘

문자열 검색 알고리즘으로 보통 ABC라는 문자열이 ABCDEFG과 같은 문자열에 포함여부를 알기 위해서는 시간 복잡도가 O(NM) 정도로 상당한 복잡도를 보이는 데 반해 KMP 알고리즘을 사용하게 되면 불필요한 계산을 건너뛰기 떄문에 복잡도를 O(N+M) 정도로 줄일 수 있다 

 

접두사와 접미사

이 KMP 알고리즘을 이해하기 위해서는 먼저 접두사와 접미사에 대한 개념을 짚고 넘어가야 한다

접두사는 말그대로 문자열의 앞에 붙은 패턴을 의미하고 접미사는 문자열의 끝에 붙어있는 패턴을 의미한다

 

이것을 예로 들어 설명하면,

"ABCDABC"라는 패턴이 있다면 접두사로 ABC, 접미사로 ABC가 패턴이 동일하게 반복되는 것을 알 수 있다.

 

KMP 알고리즘에서는 위와 같은 접두사와 접미사가 같은 패턴을 이용하여 계산을 줄이는 것이다

 

이를 좀 더 자세하게 설명하면, 

 

"ABABEABCABC"와 같은 패턴이 있는데 ABABF의 포함 여부를 검사할 때 

"ABAB"를 검사한 뒤 E 여부를 계산할 때 틀린 것을 알 수 있다.

그 이후, 반복문을 이용하여 검사할 경우 BCDEA CDEA~와 같이 검사를 해 나갈 것이다.

이 때 해당 실패한 경우에 대한 패턴을 알고 있는데 이 정보를 활용하지 못하고 처음부터 다시 검사를 시작하고 있는 것을 알 수 있다.

KMP 알고리즘은 이러한 실패 경험을 바탕으로 계산을 줄이는 것이다.

 

문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

 

풀이

위의 KMP 알고리즘을 이용하여 make_table이라는 문자열 패턴에 대한 테이블 정보를 기록해놓고

KMP 알고리즘에 해당 테이블을 이용하여 정답을 구해준다

 

# pi배열을 만드는 함수
# 이렇게 kmp 알고리즘은 틀렸다는 사실이 아니라 조금이라도 일치했었다는 정보에 주목하고 미리 전처리 해둔 pi배열을 이용해서 많은 중간 시도를 껑충 건너띌 수 있게 합니다.


# 접두사와 접미사가 같은 것을 찾아내는 게 포인트
def make_table():
    table=[0]*len(P) # 문자열의 실패를 경험 삼은 패턴 수
    j=0 # 이전의 성공 정보를 저장

    for i in range(1,len(P)): # 1부터 시작해야 한다 0부터는 의미 x
        while j>0 and P[i]!=P[j]: # 문자열이 같지 않을 떄
            j=table[j-1] # 이전까지 같았던 문자의 개수로 만들어준다
        if P[i]==P[j]: # 문자열이 같을 때
            j+=1
            table[i]=j
    return table
    # 이것의 의미를 보면 ABAB 라는 패턴이 있을 때 p[2]의 경우 앞서 두 경우를 비교하지 않아도 이미 포함되어 있다고 생각한다
    # ABCDAB가 있다면 실패의 경험을 삼아 P[5]=2,라고 할 수 있다. 
    # 문자열 안에서 시작했을 떄 몇 개를 생략할 수 있는지에 대한 정보를 TABLE에 심어준다

def KMP():
    table=make_table()
    j=0
    
    for i in range(0,len(S)):
        while j>0 and S[i]!=P[j]:
            j=table[j-1]
        if S[i]==P[j]: # 문자열이 같을 때 
            if j==len(P)-1:
                return True
            else:
                j+=1
        
    


S=input()
P=input()

if KMP():
    print(1)
else:
    print(0)