부분 문자열 [백준 16916] - python

import sys
input = sys.stdin.readline

def BOJ16916() :
  # 접두사와 접미사 개념
  def make_table(pattern) :
    table = [0 for _ in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)) :
      while j > 0 and pattern[i] != pattern[j] :
        j = table[j-1]
      if pattern[i] == pattern[j] :
        j += 1
        table[i] = j

    return table

  def KMP(parent, pattern, table) :
    j = 0

    for i in range(len(parent)) :
      while j > 0 and parent[i] != pattern[j] :
        j = table[j-1]
      
      if parent[i] == pattern[j] :
        if j == len(pattern) - 1 :
          return True
        
        j += 1

    return False

  S = input().strip()
  P = input().strip()
  table = make_table(P)
  
  if (KMP(S, P, table)) :
    print(1)
  else :
    print(0)

BOJ16916()

 

풀이 접근 방법 :

1. 첫번째 시도는 string in string 을 통해 제출을 하였다. pypy3 에서는 통과하지 못했고 python3에서는 통과가 되었다.

2. 1번 처럼 푸는 문제는 아닐것 같아 kmp 알고리즘이라는 것을 적용하기로 했다.

3. kmp 알고리즘은 문자열 매칭 알고리즘이다. O(n)의 시간복잡도를 가진다.

매번 하나씩 문자를 비교하다 보면 O(n^2)의 시간복잡도를 가지게 될것이다. 

kmp를 상세히 아는것 보다는 문자열 매칭을 시간복잡도 O(n)으로 해결할 수 있다는 것을 아는게 중요할것 같다.

 

kmp 외에는 문자열의 hash를 비교하여 풀이 접근을 시도할수도 있을것 같다.

 

 

https://www.acmicpc.net/problem/16916

16916번: 부분 문자열

 

출처 : https://bbbyung2.tistory.com/77

[Python] [백준] 16916번: 부분 문자열