[5.29] 07-2 KMP법 Knuth Morris Pratt

KMP법 알아보기

브루트 포스법보다 효율적이다. 

검사했던 결과를 버리지 않고 활용하기 때문이다. 

'몇 번째 문자부터 다시 검색할 것인지'를 표로 만들어 문제를 해결한다. 

KMP법에서 사용하는 표 만들기 skip table

#KMP법으로 문자열 검색하기

def kmp_match(txt:str, pat:str) -> int:
  pt = 1
  pp = 0
  skip = [0] * (len(pat)+1)

  skip[pt] = 0
  while pt != len(pat):
    if pat[pt] == pat[pp]:
      pt += 1
      pp += 1
      skip[pt] = pp
    elif pp == 0:
      pt += 1
      skip[pt] = pp
    else:
      pp = skip[pp]
  
  pt = pp = 0
  while pt != len(txt) and pp != len(pat):
    if txt[pt] == pat[pp]:
      pt += 1
      pp += 1
    elif pp == 0:
      pt += 1
    else:
      pp = skip[pp]
  return pt - pp if pp == len(pat) else -1

if __name__ == '__main__':
  s1 = input('텍스트를 입력하세요 : ')
  s2 = input('패턴을 입력하세요 : ')

  idx = kmp_match(s1, s2)

  if idx == -1:
    print('패턴이 존재하지 않음')
  else:
    print(f'{(idx+1)}번째 문자가 일치합니다.')