用于字谜子串搜索的 Python 程序

pythonserver side programmingprogramming

在本文中，我们将了解下面给出的问题陈述的解决方案。

问题陈述 − 给定一个文本和一个模式，我们需要在文本中打印出模式及其排列(或字谜)的所有出现情况。

现在让我们观察下面实现中的解决方案 −

示例

# 最大值
MAX = 300
# 比较
def compare(arr1, arr2):
   for i in range(MAX):
      if arr1[i] != arr2[i]:
         return False
   return True
# 搜索
def search(pat, txt):
   M = len(pat)
   N = len(txt)
   # countP 模式帐户
   # countTW 文本窗口计数
   countP = [0]*MAX
   countTW = [0]*MAX
   for i in range(M):
      (countP[ord(pat[i]) ]) += 1
      (countTW[ord(txt[i]) ]) += 1
   # 遍历
   for i in range(M, N):
      # 比较当前窗口和模式计数
      if compare(countP, countTW):
         print("Found at Index", (i-M))
      # 将字符添加到窗口
      (countTW[ ord(txt[i]) ]) += 1
      # 从窗口中删除字符
      (countTW[ ord(txt[i-M]) ]) -= 1
   # 检查最后一个窗口
   if compare(countP, countTW):
      print("它在索引处找到:", N-M)
# main
txt = "TUTORIALSPOINT"
pat = "TOR"
search(pat, txt)