ในปัญหานี้ เราจะได้รับข้อความขนาด n หนึ่งข้อความและรูปแบบขนาด m อีก 2 สตริง งานของเราคือการสร้างโปรแกรมสำหรับการค้นหาสตริงย่อยของ Anagram
ที่นี่ เราต้องค้นหาการเกิดของรูปแบบและการเรียงสับเปลี่ยนทั้งหมด (แอนนาแกรม) ในข้อความ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
text = “xyztrwqyzxfg” pattern = “xyz”
ผลลัพธ์
Found at index 0 Found at index 7
ในการแก้ปัญหานี้ เราจะต้องใช้อัลกอริทึมที่คล้ายกับ อัลกอริทึมของ Rabin Karp ซึ่งใช้ตรวจสอบการเกิดแอนนาแกรมโดยการเพิ่มค่า 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("\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;
} ผลลัพธ์
Searching Anagram pattern in the string Pattern found at index value: 0 Pattern found at index value: 7
