用于 Anagram 子串搜索的 C 程序

  • Z时代
  • 2024-01-10
  • 分类：综合

在这个问题中，我们给出了两个字符串，一个是 n 大小的文本，另一个是 m 大小的模式。我们的任务是为 Anagram 子串搜索创建一个程序。

在这里，我们必须找到文本中所有出现的模式及其所有排列（字谜）。

让我们举个例子来理解这个问题，

输入

text = “xyztrwqyzxfg” pattern = “xyz”
输出结果
Found at index 0
Found at index 7

为了解决这个问题，我们将不得不使用类似于Rabin Karp 算法的算法，该算法用于通过将所有字符的 ASCII 值相加到数字的模下来检查字谜出现。然后使用特征集窗口并匹配总和。

该解决方案将需要两个数组，用于存储文本窗口中字符的频率以及匹配模式。然后我们将窗口滑动一个并匹配每个寡妇的字符频率和匹配模式的打印。

字谜子串搜索程序

// Anagram 子串搜索程序

示例

#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

以上是 用于 Anagram 子串搜索的 C 程序 的全部内容， 来源链接： utcz.com/z/327637.html

回到顶部