字谜图案搜索

字谜基本上是给定字符串或模式的所有排列。这种模式搜索算法略有不同。在这种情况下，不仅搜索精确的模式，还会搜索文本中给定模式的所有可能排列。

为了解决这个问题，我们将整个文本分为几个长度与图案相同的窗口。然后依靠模式的每个字符找到并存储在数组中。对于每个窗口，我们还尝试找到count数组，然后检查它们是否匹配。

字谜模式搜索算法的时间复杂度为O(n)。

输入输出

Input:
The main String “AABAACBABBCABAABBA”. The pattern “AABC”.
Output:
Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10

算法

anagramSearch(text, pattern)

输入- 主字符串和模式

输出-找到模式及其所有字谜的所有位置。

Begin
   define patternFreq array and stringFreq array
   patLne := length of pattern
   stringLen := length of the text
   set all entries of patternFreq array to 0

   for all characters present in pattern, do
      increase the frequency.
   done

   for i := 0 to i<= stringLen – patLen, do
      set all entries of stringFreq to 0
      for all characters of each window, do
         increase the frequency
      done

      if the stringFreq and patternFreq are same, then
         display the value of i, as anagram found at that location
   done
End

示例

#include<iostream>
#include<cstring>
#define LETTER 26
using namespace std;

bool arrayCompare(int *array1, int *array2, int n) {
   for(int i = 0; i<n; i++) {
      if(array1[i] != array2[i])
         return false; //if there is one mismatch stop working
   }
   return true; //arrays are identical
}

void setArray(int *array, int n, int value) {
   for(int i = 0; i<n; i++)
      array[i] = value; //put value for all places in the array
}

void anagramSearch(string mainString, string patt, int *array, int *index) {
   int strFreq[LETTER], pattFreq[LETTER];
   int patLen = patt.size();
   int stringLen = mainString.size();
   setArray(pattFreq, LETTER, 0);    //initialize all frequency to 0

   for(int i = 0; i<patLen; i++) {
      int patIndex = patt[i] - 'A';   //subtract ASCII of A
      pattFreq[patIndex]++;           //increase frequency
   }

   for(int i = 0; i<=(stringLen - patLen); i++) {    //the range where window will move
      setArray(strFreq, LETTER, 0);         //initialize all frequency to 0 for main string
      for(int j = i; j<(i+patLen); j++){    //update frequency for each window.
         int strIndex = mainString[j] - 'A';
         strFreq[strIndex]++;               //increase frequency
      }

      if(arrayCompare(strFreq, pattFreq, LETTER)) {    //when both arrays are identical
         (*index)++;
         array[*index] = i;           //anagram found at ith position
      }
   }
}

int main() {
   string mainStrng = "AABAACBABBCABAABBA";
   string pattern = "AABC";
   int matchLocation[mainStrng.size()];
   int index = -1;
   anagramSearch(mainStrng, pattern, matchLocation, &index);

   for(int i = 0; i<=index; i++) {
      cout << "Anagram found at position: " << matchLocation[i] << endl;
   }

}

输出结果

Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10