Tìm hàng trùng lặp trong ma trận nhị phân C++

Cho ma trận nhị phân. Tìm các hàng trùng lặp. Ví dụ ma trận 6×6 có hàng trùng ở vị trí 3, 4, 5 (đánh chỉ số từ 0).

Cây Trie nhị phân

Chèn từng hàng vào Trie (nhánh 0 và 1). Nếu khi chèn gặp nút lá đã tồn tại → hàng trùng lặp.

Ví dụ minh họa

#include <iostream>
using namespace std;

const int MAX = 100;

struct Trie {
    bool isLeaf = false;
    Trie* child[2] = {nullptr, nullptr};
};

Trie* newNode() { return new Trie(); }

bool insert(Trie* root, bool row[], int n) {
    Trie* cur = root;
    for (int i = 0; i < n; i++) {
        int b = row[i];
        if (!cur->child[b]) cur->child[b] = newNode();
        cur = cur->child[b];
    }
    if (cur->isLeaf) return false;  // đã tồn tại
    return cur->isLeaf = true;
}

void findDuplicates(bool mat[][MAX], int rows, int cols) {
    Trie* root = newNode();
    for (int i = 0; i < rows; i++)
        if (!insert(root, mat[i], cols))
            cout << "Hang trung lap tai vi tri: " << i << endl;
}

int main() {
    bool mat[][MAX] = {
        {1,1,0,1,0,1},
        {0,0,1,0,0,1},
        {1,0,1,1,0,0},
        {1,1,0,1,0,1},
        {0,0,1,0,0,1},
        {0,0,1,0,0,1}
    };
    findDuplicates(mat, 6, 6);
    return 0;
}

Kết quả

Hang trung lap tai vi tri: 3
Hang trung lap tai vi tri: 4
Hang trung lap tai vi tri: 5