資料結構
網路
RDBMS
作業系統
Java
Microsoft 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-Jun-2020
424 次瀏覽
廣告