動機

雖然說現在它的主場只存在於課本中，但好像還是有人喜歡問… 改成用遞迴比較好懂

之後還有Boyer–Moore algorithm阿 good suffix真的不好懂

naive

每次失敗就從頭開始

def fail(j):
  return 0

def match(s,p):
  j = 0
  i = 0
  while i < len(s):
    if j == len(p):
      print("match at {}".format(i))
      return
    elif s[i] == p[j]:
      j += 1
      i += 1
    elif j == 0:
      i += 1
    else:
      j = fail(j)
  print("no match")

Knuth-Morris-Pratt algorithm

如果pattern裡面有重複的，可以移過去!! 像是abababb，如果在最後一個a出事，下一個應該要從第二個的前一位開始

所以我們假設fail給到目前為止成功的位置，會給出下一次要從哪邊開始 有兩個case

  1. 在起點(0)成功或是失敗，就是從頭開始
  2. 在其他地方成功
  • 往已經比完的地方看，一直往前看給出的下一個位置的字是不是與比對成功的字一樣
    • 一樣就可以回傳該位置加一(字一樣會比對失敗，所以要下一位)
    • 不一樣就是比對失敗，從頭開始，也因為loop的條件，所以只要一直不一樣最後就會是0
@functools.lru_cache(None)
def fail(p,i):
  if i <= 0:
    return 0
  else:
    j = fail(i-1)
    while j > 0 and p[j] != p[i]:
      j = fail(j-1)
    return j+(1 if p[j] == p[i] else 0)
    
def match(s,p):
  j = 0
  i = 0
  while i < len(s):
    if j == len(p):
      print("match at {}".format(i))
      return
    elif s[i] == p[j]:
      j += 1
      i += 1
    elif j == 0:
      i += 1
    else:
      j = fail(j-1)
  print("no match")