Chương trình C tìm anagram con trong chuỗi

Trong bài toán này, chúng ta được cho hai chuỗi: một chuỗi văn bản (text) kích thước n và một chuỗi mẫu (pattern) kích thước m. Nhiệm vụ là viết chương trình tìm anagram con (Anagram substring search).

Chúng ta cần tìm tất cả các lần xuất hiện của mẫu và tất cả các hoán vị (anagram) của nó trong văn bản.

Ví dụ minh họa bài toán:

Đầu vào

text = "xyztrwqyzxfg" pattern = "xyz"

Đầu ra

Found at index 0 Found at index 7

Để giải quyết, sử dụng thuật toán tương tự Rabin-Karp: kiểm tra xuất hiện anagram bằng cách cộng giá trị ASCII của các ký tự trong cửa sổ dưới modulo một số. Sau đó dùng cửa sổ trượt và so sánh tổng.

Giải pháp cần hai mảng lưu tần suất ký tự trong cửa sổ văn bản và mẫu. Trượt cửa sổ một đơn vị, so sánh tần suất ký tự cho mỗi cửa sổ và in ra khi khớp.

Chương trình tìm Anagram Substring Search

// Chương trình tìm Anagram Substring Search

Ví dụ

#include 
#include 
#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;
}

Kết quả

Searching Anagram pattern in the string
Pattern found at index value: 0
Pattern found at index value: 7