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

この問題では、サイズnのテキストとサイズmのパターンの2つの文字列が与えられます。私たちの仕事は、アナグラムの部分文字列検索用のプログラムを作成することです。

ここでは、テキスト内のすべてのパターンの出現とそのすべての順列（アナグラム）を見つける必要があります。

問題を理解するために例を見てみましょう

入力

text = “xyztrwqyzxfg” pattern = “xyz”

出力

Found at index 0
Found at index 7

この問題を解決するには、ラビンカープアルゴリズムと同様のアルゴリズムを使用する必要があります。 これは、数値を法としてすべての文字のASCII値を加算することにより、アナグラムの出現をチェックするために使用されます。次に、特性セットのウィンドウを使用して、合計を照合します。

このソリューションでは、テキストのウィンドウ内の文字の頻度と一致するパターンを格納する2つの配列が必要になります。次に、ウィンドウを1つずつスライドさせて、各未亡人の文字頻度を一致させ、一致するパターンを印刷します。

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

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

例

#include <cstring>
#include <iostream>
#define MAX 256
using namespace std;
bool matchPattern(char arr1[], char arr2[]){
   for (int i = 0; i < MAX; i++)
   if (arr1[i] != arr2[i])
      return false;
   return true;
}
void anagramSearch(char* pattern, char* text){
   int M = strlen(pattern);
   int N = strlen(text);
   char patternArray[MAX] = { 0 }, textArray[MAX] = { 0 };
   for (int i = 0; i < M; i++) {
      (patternArray[pattern[i]])++;
      (textArray[text[i]])++;
   }
   for (int i = M; i < N; i++) {
      if (matchPattern(patternArray, textArray))
         printf("\nPattern found at index value : %d", (i-M));
      (textArray[text[i]])++;
      textArray[text[i - M]]--;
   }
   if (matchPattern(patternArray, textArray))
   printf("\nPattern found at index value: %d", (N-M));
}
int main() {
   char text[] = "xyztrwqyzxfg";
   char pattern[] = "xyz";
   printf("Searching Anagram pattern in the string ");
   anagramSearch(pattern, text);
   return 0;
}

出力

Searching Anagram pattern in the string
Pattern found at index value: 0
Pattern found at index value: 7