資料結構
網路
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 次瀏覽
廣告