Anagram Pattern Search (การค้นหาแอนนากราม)

Anagram Pattern Search ค้นหาทุกตำแหน่งใน Text ที่มี Anagram (การจัดเรียงตัวอักษรใหม่) ของ Pattern ปรากฏขึ้น ไม่ใช่ค้นหา Pattern ตรงๆ

แนวคิดการทำงาน

1. สร้าง Frequency Array ของ Pattern (ขนาด 26 สำหรับ A-Z)
2. Sliding Window ขนาด = Pattern Length วิ่งผ่าน Text
3. สร้าง Frequency Array ของแต่ละ Window
4. เปรียบเทียบ 2 Frequency Array → ตรงกัน = พบ Anagram

ตัวอย่างข้อมูล

Text:    AABAACBABBCABAABBA
Pattern: AABC

Anagrams of AABC: AABC, AACB, ABAC, ABCA, ACAB, ACBA, BAAC, BACA, BCAA, CAAB, CABA, CBAA

Output:
Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10

อัลกอริทึม (Pseudocode)

anagramSearch(text, pattern)
  patFreq[26] = {0}
  for each char c in pattern:
    patFreq[c-'A']++

  for i = 0 to text.length - pattern.length:
    strFreq[26] = {0}
    for j = i to i+pattern.length-1:
      strFreq[text[j]-'A']++
    if strFreq == patFreq:
      report anagram at position i

ตัวอย่างโค้ด C++

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

#define LETTER 26

bool compareArrays(int *a, int *b, int n) {
    for (int i = 0; i < n; i++)
        if (a[i] != b[i]) return false;
    return true;
}

void anagramSearch(string text, string pattern) {
    int patFreq[LETTER] = {0};
    for (char c : pattern) patFreq[c - 'A']++;

    int n = text.size(), m = pattern.size();

    for (int i = 0; i <= n - m; i++) {
        int strFreq[LETTER] = {0};
        for (int j = i; j < i + m; j++)
            strFreq[text[j] - 'A']++;

        if (compareArrays(strFreq, patFreq, LETTER))
            cout << "Anagram found at position: " << i << endl;
    }
}

int main() {
    string text = "AABAACBABBCABAABBA";
    string pattern = "AABC";
    anagramSearch(text, pattern);
}

การปรับปรุงประสิทธิภาพ: Sliding Window + Incremental Update

แทนที่จะสร้าง Frequency Array ใหม่ทุก Window ให้อัปเดตแบบ Incremental:

// Initial window
for (int j = 0; j < m; j++) strFreq[text[j]-'A']++;

for (int i = 0; i <= n-m; i++) {
    if (compareArrays(strFreq, patFreq, LETTER))
        report i;

    // Slide window
    if (i + m < n) {
        strFreq[text[i]-'A']--;       // Remove leftmost
        strFreq[text[i+m]-'A']++;     // Add new rightmost
    }
}

ลด Time จาก O(n·m) เป็น O(n + m) ≈ O(n)

ความซับซ้อน

• Naive: O(n·m·α) โดย α = alphabet size
• Optimized Sliding Window: O(n·α) ≈ O(n)
• Space: O(α)

การประยุกต์ใช้

• Bioinformatics: ค้นหา DNA motifs
• Plagiarism detection
• Cryptanalysis
• Word games (Scrabble, Anagram solvers)