Đếm số lần xuất hiện của chuỗi cho trước trong mảng ký tự 2D bằng C++

Bài toán sau là ví dụ điển hình của ô chữ hàng ngày: cho một mảng ký tự 2 chiều, nhiệm vụ là tìm từ khóa cho trước trong mê cung mảng ký tự 2D này. Thuật toán tìm kiếm bao gồm việc tìm các ký tự riêng lẻ theo các hướng Trên-xuống, Phải-trái và ngược lại nhưng không theo đường chéo.

Hiểu qua ví dụ

Đầu vào: Từ khóa word = "LAYS"

Mảng 2D: { "LOAPYS", "KAYSOT", "LAYSST", "MLVAYS", "LAYSAA", "LAOYLS" }

Đầu ra: Số lần xuất hiện chuỗi trong mảng 2D: 7

Giải thích: Từ "LAYS" có thể tìm thấy theo các hướng Trên-Dưới, Phải-Trái, Dưới-Trên, Trái-Phải. Biến đếm tăng mỗi khi tìm thấy chuỗi. Trong ví dụ, "LAYS" xuất hiện 7 lần:

1. LOAPYS - LAYS (Trái sang Phải)
2. SAYAOL - LAYS (Phải sang Trái)
3. LAYSST - LAYS (Trái sang Phải)
4. MLVAYS - LAYS (Trái sang Phải)
5. LAYSAA - LAYS (Trái sang Phải)
6. LAOYLS - LAYS (Trái sang Phải)
7. (Dưới lên Trên) LAYS

Đầu vào: Từ khóa word = "CAMP"

Mảng 2D: { "BLOOKS", "BPOOLK", "KOHPKB", "BOLKOK", "LKIOOB", "LAHYBL" }

Đầu ra: Số lần xuất hiện: 0

Giải thích: Không tìm thấy từ "LAYS" (lưu ý: văn bản gốc nhắc đến "BOOK" nhưng ví dụ dùng "CAMP").

Phương pháp sử dụng

• Cho một chuỗi (word) và mảng chuỗi cùng các biến tiện ích truyền vào hàm findString() để xử lý.
• Duyệt các ký tự trong ma trận, chọn một ký tự làm điểm bắt đầu.
• Từ ký tự đã chọn, tìm đệ quy chuỗi cho trước theo tất cả các hướng cho phép.
• Nếu khớp, tăng biến đếm.
• Lặp lại quá trình cho ký tự bắt đầu tiếp theo.
• Tổng hợp số lượng khớp tìm được.
• In kết quả cuối cùng.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 

int utilitySearch(string word, int r, int c, string arr[], int maxR, int maxC, int index) { 
    int count = 0; 
    if (r >= 0 && r <= maxR && c >= 0) { 
        if (c <= maxC && word[index] == arr[r][c]) { 
            char res = word[index]; 
            index = index + 1; 
            arr[r][c] = 0; 
            if (word[index] == 0) { 
                count = 1; 
            } else { 
                count = count + utilitySearch(word, r, c + 1, arr, maxR, maxC, index); 
                count = count + utilitySearch(word, r, c - 1, arr, maxR, maxC, index); 
                count = count + utilitySearch(word, r + 1, c, arr, maxR, maxC, index); 
                count = count + utilitySearch(word, r - 1, c, arr, maxR, maxC, index); 
            } 
            arr[r][c] = res; 
        } 
    } 
    return count; 
} 

int findString(string word, int r, int c, string str[], int countR, int countC) { 
    int count = 0; 
    for (int i = 0; i < countR; ++i) { 
        for (int j = 0; j < countC; ++j) { 
            count = count + utilitySearch(word, i, j, str, countR - 1, countC - 1, 0); 
        } 
    } 
    return count; 
} 

int main() { 
    string word = "FLOOD"; 
    string inp[] = {"FPLIOKOD", "FLOODYUT", "YFLOODPU", "FMLOSODT", "FILPOYOD", "FLOOOODE"}; 
    string str[(sizeof(inp) / sizeof(*inp))]; 
    for (int i = 0; i < (sizeof(inp) / sizeof(*inp)); ++i) { 
        str[i] = inp[i]; 
    } 
    cout << "Count of number of given string in 2D character array: " << findString(word, 0, 0, str, (sizeof(inp) / sizeof(*inp)), str[0].size()); 
    return 0; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of number of given string in 2D character array: 6