資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究異位模式查詢
異位詞基本上是給定的字串或模式的所有排列。此模式查詢演算法略有不同。在這種情況下，不僅要搜尋精確的模式，還要在文字中搜索給定模式的所有可能排列。
要解決這個問題，我們將把整個文字分成幾個長度與模式相同的視窗。然後計算模式的每個字元出現的位置並將其儲存在陣列中。對於每個視窗，我們還嘗試找到計數陣列，然後檢查它們是否匹配。
異位模式查詢演算法的時間複雜度為 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
更新於：15-06-2020
424 次瀏覽
廣告