数据结构
网络
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 次浏览
广告