아나그램 패턴 검색

애너그램은 기본적으로 주어진 문자열이나 패턴의 모든 순열입니다. 이 패턴 검색 알고리즘은 약간 다릅니다. 이 경우 정확한 패턴만 검색되는 것이 아니라, 텍스트에서 주어진 패턴의 가능한 모든 배열을 검색합니다.

이 문제를 해결하기 위해 전체 텍스트를 패턴과 같은 길이의 여러 창으로 나눕니다. 그런 다음 패턴의 각 문자를 카운트하여 배열에 저장합니다. 또한 각 창에 대해 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