アナグラム部分文字列検索用のPythonプログラム

この記事では、以下に示す問題ステートメントの解決策について学習します。

問題の説明 −テキストとパターンが与えられた場合、パターンのすべての出現とその順列（またはアナグラム）をテキストで印刷する必要があります。

次に、以下の実装のソリューションを見てみましょう-

例

# maximum value
MAX = 300
# compare
def compare(arr1, arr2):
   for i in range(MAX):
      if arr1[i] != arr2[i]:
         return False
   return True
# search
def search(pat, txt):
   M = len(pat)
   N = len(txt)
   # countP pattern account
   # countTW text window count
   countP = [0]*MAX
   countTW = [0]*MAX
   for i in range(M):
      (countP[ord(pat[i]) ]) += 1
      (countTW[ord(txt[i]) ]) += 1
   # Traversal
   for i in range(M, N):
      # Compare current window and patten counts
      if compare(countP, countTW):
         print("Found at Index", (i-M))
      # Add charcter to window
      (countTW[ ord(txt[i]) ]) += 1
      # remove charcter from window
      (countTW[ ord(txt[i-M]) ]) -= 1
   # Check for the last window
   if compare(countP, countTW):
      print("It is Found at Index : ", N-M)
# main
txt = "TUTORIALSPOINT"
pat = "TOR"
search(pat, txt)

出力

Found at Index 2

すべての変数はローカルスコープで宣言されており、それらの参照は上の図に示されています。

結論

この記事では、アナグラム部分文字列検索用のPythonプログラムを作成する方法について学習しました。