字符串匹配算法

  1. def brute_force(t: str, p: str):
  2.     # 暴力破解
  3.     i = 0
  4.     while i < len(t):
  5.         j = 0
  6.         while j < len(p):
  7.             if t[i + j] != p[j]:
  8.                 break
  9.             j = j + 1
  10.         if j == len(p):
  11.             return i
  13.         i = i + 1
  14.     return False
  17. def brute_force1(s: str, p: str):
  18.     # aaaab, aaab
  19.     # 暴力破解, 很接近kmp+3
  20.     i = 0
  21.     j = 0
  22.     temp = 0
  23.     while i < len(s) and j < len(p): # 考虑去掉一重f循环， 当内外层循环控制变量会有某种联系时候
  24.         if (s[i] == p[j]):
  25.             j = j + 1
  26.             temp = temp + 1
  27.         else:  # 当前匹配失败（j的更新没有考虑前后缀问题)
  28.             j = 0  # 恢复j
  29.             i = i - temp  # 恢复i
  30.             temp = 0
  31.         i = i + 1
  33.     if j == len(p):
  34.         return i - len(p)
  35.     else:
  36.         return False
  39. def get_next(p: str) -> []:
  40.     # 基于前缀后缀
  41.     #
  42.     next: list[int] = [0]
  43.     count = 0
  44.     i = 0
  45.     j = 0
  46.     s = p[1:]
  47.     p = p[:len(p) - 1]
  48.     while i < len(s):
  49.         # i 控制的是 当前 串的后缀， j 是前缀。只考虑当前串， 后缀某个字符开始， 和字符串开头字符开始匹配， 取其最大， 称为最大公共字串
  50.         if (s[i] == p[j]):
  51.             j = j + 1
  52.             next.append(j)
  53.         else:  #
  54.             if j == 0: # s_i ! = p_j and j == 0  表示第一个就匹配不上, 必定没有公共缀
  55.                 next.append(j)
  56.             else: # s_i != p_J and j != 0 可能从头还会匹配上， 保持i
  57.                 j = 0
  58.                 continue
  60.         i = i + 1
  61.     return next
  67. def kmp(s: str, p: str) -> bool:
  68.     i = 0
  69.     j = 0
  70.     next = get_next(p)
  71.     while i < len(s) and j < len(p):
  72.         if (s[i] == p[j]):
  73.             j = j + 1
  74.         else:  #
  75.             j = next[j - 1] + 1
  77.         i = i + 1
  78.     if j == len(p):
  79.         return i - len(p)
  80.     else:
  81.         return False
  83. if __name__ == '__main__':
  84.     print(brute_force('helloworld', 'world'))
  85.     print(brute_force1('helloworld', 'world'))
  86.     print(kmp('helloworld', 'world'))
  89. s = 'aaaab'
  90. p = 'aaab'
  91. print(kmp(s, p))

总结

  • 双重循环， 考虑去掉一重
  • 从暴力开始优化