boj 16916 [kmp 알고리즘]

boj 16916 - △

📌생각 logic

1. s에서 p의 접두사를 find
2. p의 길이 len(p)만큼 문자열이 일치하는지 비교
3. 없으면 0, 맞으면 1 return

❗️ERROR point

1. 문자열을 일일이 비교하면(브루트포스) 시간초과
2. find 함수를 쓰면 s에 존재하는 첫 번째 문자만 반환되기 때문에 같은 문자가 여러개 있을 시 찾을 방법 hard

📍KMP 알고리즘

문자열 검색 알고리즘 (string matching)

브루트포스로 p를 s 인덱스 하나씩 옮겨가면서 비교하면 시간이 너무 오래걸림
브루트포스 시간복잡도 : O(n*m)
kmp 알고리즘 시간복잡도 : O(n+m)

• pi배열로 찾고자 하는 문자열의 한 문자가 그 전에도 존재했는지 확인
  -> 이를 통해 비교하고자 하는 문자열과 비교했을 때, 다시 처음부터 중복되게 비교하는 과정을 덜고자 함

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")

다른 문제 하나 더 풀어보고 완벽히 이해해서 정리본 올릴 것!

참고

• https://bowbowbow.tistory.com/6