python3 kmp 字符串匹配的方法

text_str = 'asdabcdace'
pat_str = 'abcdace'

def str_match(text_str,pat_str):
  for i in range(0,len(text_str)):
    j = 1
    while j < len(pat_str):
      if text_str[i:i+j] != pat_str[0:j]: #從text_str第i個字符開始，看匹配是否成功
        break  #匹配失敗，直接跳出循環(huán)，i+1，繼續(xù)從第一個字符匹配
      j += 1   #匹配成功就繼續(xù)匹配下一個字符，知道pat_str每個字符都匹配完
    if j == len(pat_str):
      return i
  return -1

print(str_match(text_str,pat_str))

#求字符串的next值
text_str = 'asdabcdace'
pat_str = 'abcdace'

#得到字符對應(yīng)的next值
def str_next(s):
  #前兩個字符默認(rèn)等于1
  next = [1,1]
  for x in range(2,len(s)):
    next.append(str_max_prx(s,x,next[x-1]-1) + 1)
  return next
#參數(shù) s字符串，匹配進行到的位置，下次開始匹配的位置
def str_max_prx(s,x,last_value):
  next = 0
  for i in range(last_value,x):
    if s[0:i] == s[x-i:x]:
      next = i
  return next
def str_match(s,m):
  next = str_next(s)
  i=0
  s_len = len(s)
  m_len = len(m)
  while i <= m_len:
    flag = True   #標(biāo)志位，用來判斷是否匹配成功
    index = 1
    while index <= s_len:
      if m[i:i + index] != s[0:index]:
        i = i + next[index]
        flag = False
        break
      else:
        index += 1
    if flag:
      break
  if i >= m_len:
    i = -1
  return i
res = str_match(pat_str,text_str)
print(res)