Tìm kiếm mẫu đảo ngữ

Đảo ngữ về cơ bản là tất cả các hoán vị của một chuỗi hoặc mẫu nhất định. Thuật toán tìm kiếm mẫu này hơi khác một chút. Trong trường hợp này, không chỉ tìm kiếm mẫu chính xác mà còn tìm kiếm tất cả các cách sắp xếp có thể có của mẫu đã cho trong văn bản.

Để giải quyết vấn đề này, chúng tôi sẽ chia toàn bộ văn bản thành nhiều cửa sổ có độ dài giống như các mẫu. Sau đó, đếm từng ký tự của mẫu được tìm thấy và lưu trữ trong một mảng. Đối với mỗi cửa sổ, chúng tôi cũng cố gắng tìm mảng đếm, sau đó kiểm tra xem chúng có khớp hay không.

Độ phức tạp về thời gian của Thuật toán tìm kiếm mẫu đảo ngữ là O (n).

Đầu vào và Đầu ra

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

Thuật toán

anagramSearch(text, pattern)

Đầu vào - Chuỗi chính và mẫu

Đầu ra - Tất cả các vị trí nơi mẫu và tất cả các từ đảo ngữ được tìm thấy.

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

Ví dụ

#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;
   }

}

Đầu ra

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