Trong bài toán này, chúng ta được cung cấp cho hai chuỗi một văn bản có kích thước n và một mẫu khác có kích thước m. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm kiếm chuỗi con Anagram.
Ở đây, chúng ta phải tìm tất cả sự xuất hiện của mẫu và tất cả các hoán vị của nó (đảo chữ) trong văn bản.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
text = “xyztrwqyzxfg” pattern = “xyz”
Đầu ra
Found at index 0 Found at index 7
Để giải quyết vấn đề này, chúng ta sẽ phải sử dụng một thuật toán tương tự như thuật toán Rabin Karp được sử dụng để kiểm tra sự xuất hiện của đảo chữ bằng cách thêm các giá trị ASCII của tất cả các ký tự theo mô-đun của một số. và sau đó sử dụng một cửa sổ tập hợp các đặc điểm và so khớp với tổng.
Giải pháp sẽ yêu cầu hai mảng để lưu trữ tần số của các ký tự trong cửa sổ văn bản cũng như mẫu phù hợp. Sau đó, chúng tôi sẽ trượt từng cửa sổ một và khớp các tần số ký tự cho từng góa phụ và in mẫu phù hợp.
Chương trình tìm kiếm chuỗi con Anagram
// Chương trình tìm kiếm chuỗi con Anagram
Ví dụ
#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("\nPattern found at index value : %d", (i-M));
(textArray[text[i]])++;
textArray[text[i - M]]--;
}
if (matchPattern(patternArray, textArray))
printf("\nPattern 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;
} Đầu ra
Searching Anagram pattern in the string Pattern found at index value: 0 Pattern found at index value: 7