数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律学C 程序针对异位词子串搜索
在这个问题中，我们有给定的两个字符串，一个 n 长度的文本和一个 m 长度的模式。我们的任务是为异位词子串搜索创建一个程序。
在这里，我们必须找到模式的所有出现情况以及文本中模式的所有排列（异位词）。
我们举一个例子来了解这个问题，
输入
text = “xyztrwqyzxfg” pattern = “xyz”
输出
Found at index 0 Found at index 7
为了解决这个问题，我们将不得不使用类似于拉宾·卡普算法的算法，该算法用于通过对所有字符的 ASCII 值求和在模数下检查异位词出现情况。然后使用一组特征窗口并匹配该和。
该解决方案需要两个数组，用于存储文本窗口以及匹配模式中的字符频率。然后我们将窗口滑动一个字符，并针对每个窗口匹配字符频率，并打印匹配模式。
异位词子串搜索程序
// 异位词子串搜索程序
示例
#include <cstring>
#include <iostream>
#define MAX 256
using namespace std;
bool matchPattern(char arr1[], char arr2[]){
for (int i = 0; i < MAX; i++)
if (arr1[i] != arr2[i])
return false;
return true;
}
void anagramSearch(char* pattern, char* text){
int M = strlen(pattern);
int N = strlen(text);
char patternArray[MAX] = { 0 }, textArray[MAX] = { 0 };
for (int i = 0; i < M; i++) {
(patternArray[pattern[i]])++;
(textArray[text[i]])++;
}
for (int i = M; i < N; i++) {
if (matchPattern(patternArray, textArray))
printf("
Pattern found at index value : %d", (i-M));
(textArray[text[i]])++;
textArray[text[i - M]]--;
}
if (matchPattern(patternArray, textArray))
printf("
Pattern found at index value: %d", (N-M));
}
int main() {
char text[] = "xyztrwqyzxfg";
char pattern[] = "xyz";
printf("Searching Anagram pattern in the string ");
anagramSearch(pattern, text);
return 0;
}输出
Searching Anagram pattern in the string Pattern found at index value: 0 Pattern found at index value: 7
更新于： 2020 年 7 月 17 日
210 次浏览
广告