ในปัญหานี้ เราได้รับสตริง 2 ตัว คือ text ขนาด n และ pattern ขนาด m งานของเราคือสร้างโปรแกรมสำหรับ Anagram Substring Search
ที่นี่ เราต้องหาทุกครั้งที่ pattern และการจัดเรียงใหม่ทั้งหมด (anagrams) ของมันปรากฏใน text
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
text = "xyztrwqyzxfg" pattern = "xyz"
เอาต์พุต
Found at index 0 Found at index 7
เพื่อแก้ปัญหานี้ เราจะต้องใช้อัลกอริทึมที่คล้ายกับ Rabin Karp algorithm ซึ่งใช้ตรวจสอบการเกิดของ anagram โดยการบวกค่า ASCII ของตัวอักษรทั้งหมดภายใต้ modulo ของตัวเลข และใช้ sliding window ในการจับคู่ผลรวม
วิธีแก้จะต้องใช้อาร์เรย์ 2 ตัว เพื่อเก็บความถี่ของตัวอักษรใน window ของ text และ pattern จากนั้นเราจะเลื่อน window ทีละตัวและเปรียบเทียบความถี่ตัวอักษรสำหรับแต่ละ window และพิมพ์ตำแหน่งที่ตรงกัน
โปรแกรมสำหรับ Anagram Substring Search
// Program for Anagram Substring Search
ตัวอย่าง
#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
