KMP알고리즘을 이용하는 문제
kmp알고리즘은 기본적으로 투포인터와 비슷한 맥락으로 풀이한다.
패턴부분의 접두사, 접미사의 길이를 구하고, 이를 통해서 문자열을 계산한다.
s=input()
p=input()
#p의 접두사, 접미사 구하기
l=[0 for x in range(len(p))]
i=1
j=0
while i<len(p):
while j>0 and p[j]!=p[i]:
j=l[j-1]
if p[j]==p[i]:
j+=1
l[i]=j
i+=1
j=0
for i in range(len(s)):
while (j>0 and s[i]!=p[j]):
j=l[j-1]
if s[i]==p[j]:
if j==len(p)-1:
print("1")
exit()
else:
j+=1
print("0")위의 코드에서 while i<len(p)부분이 바로 접두사와 접미사의 길이를 구하는 과정이다.
이를 통해서 l은 접두어의 좌표를 가진 배열이 된다.
l=[0 for x in range(len(p))]
i=1
j=0
while i<len(p):
while j>0 and p[j]!=p[i]:
j=l[j-1]
if p[j]==p[i]:
j+=1
l[i]=j
i+=1좌표를 구하는 과정은 기존 투포인터 방식으로,
j를 0으로 i를 1로 하여시작한다.
그리고 i를 하나씩 증가시키며 패턴문자열을 진행시키는데, 여기서
패턴문자열의 j번째 문자와 i번째 문자가 같은 경우, l[i]에 j값을 등록하고, j값을 증가시킨다.
만약 그리고 둘이 다르다면, j값을 이전 값의 j좌표로 갱신한다. 얘를들면 abac의 경우,
l[2]는 1을갖게되고, c가 b와 다르므로 j는 1로 변환된다. 그러나 c와 b도 다른 값이기 때문에 결국 j는 0이된다.
이렇게 되면 결국 l은 [0,0,1,0]이 된다.
이를 통해서 kmp알고리즘을 수행해보자. 역시 투포인터 방식과 비슷하다.
j=0
for i in range(len(s)):
while (j>0 and s[i]!=p[j]):
j=l[j-1]
if s[i]==p[j]:
if j==len(p)-1:
print("1")
exit()
else:
j+=1
print("0")예를들어 ababac(s문자열)의 문자열안에 abac(p문자열)가 포함됐는지 확인하는 경우, s문자열을 반복시켜서 i값을 증가시키며 진행한다.
j는 0으로 시작하며, j는 패턴의 진행상황을 담고 있게 된다
두 값이 같다면, j값을 증가시켜서 패턴과 원문을 계속 진행하며,
만약 두 값이 다르다면, j값을 s[i]와 p[j]가 같을때까지, 혹은 j값이 0보다 클때까지만 l[j-1]값, 즉 이전 접두사 위치로 이동시킨다.
이렇게 하여 j값이 패턴문자열과 같아지는 경우 1을 반환하고 프로그램을 종료해주었다. 있는지 없는지만 검사하므로 더이상 진행시킬 필요가 없다.
