January 24, 2023

언제 쓰지?

• 큰 문자열 내에 특정 문자열이 포함되었는지 안되었는지를 빠르게 찾기 위해 사용

KMP 알고리즘

• 문자열 매칭 알고리즘
• Brute-force를 이용할 경우, 길이가 10,000,000안 글에서 길이가 1,000인 부분 문자열을 찾으려는 경우 연산이 10,000,000,000회 필요
• KMP 알고리즘은 모든 경우의 수를 계산하지 않아도 됨
  • 불필요한 문자열을 점프

접두사와 접미사

• 접두사 : 앞에 있는 문자열 (자기 자신 제외)
• 접미사 : 뒤에 있는 문자열 (자기 자신 제외)
• 예시
  • ABACAABA
    • 접두사 : A, AB, ABA, ABAC, ABACA, ABACAA, ABACAAB
    • 접미사 : A, BA, ABA, AABA, CAABA, ACAABA, BACAABA

접두사와 접미사의 활용

• 접두사와 접미사의 개념을 활용하면 반복되는 연산을 얼마나 줄일 수 있는지 판별하여 매칭할 문자열을 빠르게 점프할 수 있다.

  • 접두사와 접미사기 일치하는 경우에 한해서는 점프를 수행할 수 있다.

• 접두사와 접미사가 일치하는 최대 길이

  길이	문자열	최대 일치 길이
  1	a	0
  2	ab	0
  3	aba	1
  4	abac	0
  5	abaca	1
  6	abacaa	1
  7	abacaab	2
  8	abacaaba	3

• 소스코드

  def make_table(pattern):
      pattern_size = len(pattern)
      table = [0] * pattern_size
  
      j = 0
  
      for i in range(1, pattern_size):
          while (j > 0 and pattern[i] != pattern[j]):
              print(j, pattern[i], pattern[j])
              j = table[j - 1]
  
          if (pattern[i] == pattern[j]):
              table[i] = j = j + 1
  
      return table
  
  pattern = "abacaaba"
  
  print(make_table(pattern))
  

소스코드