<aside> 💡

문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나

</aside>

• txt : representing the main text

• pat : representing the pattern

• e.g.,

  • Case 1
    • Input : txt = “abcab”, pat = “ab”
    • Output : [0, 3]
  • Case 2
    • Input : txt = “aabaacaadaabaaba”
    • Output : [0, 9, 12]
    • Example Image

• Code Example (Python, Naive Version)

  def search(pat, txt):
      res = []
      n = len(txt)
      m = len(pat)
  
      for i in range(n - m + 1):
          j = 0
  
          # compare pattern with substring 
          # starting at index i
          while j < m and txt[i + j] == pat[j]:
              j += 1
  
          # if full pattern matched
          if j == m:
              res.append(i)
  
      return res
  
  if __name__ == "__main__":
      txt = "aabaacaadaabaaba"
      pat = "aaba"
  
      res = search(pat, txt)
      for idx in res:
          print(idx, end=" ")
  

참고 자료

KMP Algorithm for Pattern Searching - GeeksforGeeks

KMP (Knuth-Morris-Pratt) Algorithm for Pattern Searching in C - GeeksforGeeks