ধরুন আমরা একটি বাইনারি ম্যাট্রিক্স। এখানে আমরা দেখব কিভাবে সেই ম্যাট্রিক্সে ডুপ্লিকেট সারি খুঁজে বের করা যায়। ধরুন ম্যাট্রিক্স হল −
এর মত| 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 |
অবস্থান 3, 4, 5 এ ডুপ্লিকেট সারি আছে।
এটি সমাধান করার জন্য, আমরা Trie ব্যবহার করব। Trie হল একটি দক্ষ ডাটা স্ট্রাকচার যা শক্তিশালী এবং ডেটা পুনরুদ্ধারের জন্য ব্যবহৃত হয় যেখানে ক্যারেক্টার সেট ছোট। অনুসন্ধান জটিলতা কী দৈর্ঘ্য হিসাবে সর্বোত্তম। তাই প্রথমে আমরা বাইনারি ট্রাই সন্নিবেশ করব। যদি নতুন যোগ করা সারিটি ইতিমধ্যেই উপস্থিত থাকে, তাহলে সেটি সদৃশ৷
৷উদাহরণ
#include<iostream>
using namespace std;
const int MAX = 100;
class Trie {
public:
bool leaf_node;
Trie* children[2];
};
Trie* getNode() {
Trie* node = new Trie;
node->children[0] = node->children[1] = NULL;
node->leaf_node = false;
return node;
}
bool insert(Trie*& head, bool* arr, int N) {
Trie* curr = head;
for (int i = 0; i < N; i++) {
if (curr->children[arr[i]] == NULL)
curr->children[arr[i]] = getNode();
curr = curr->children[arr[i]];
}
if (curr->leaf_node)
return false;
return (curr->leaf_node = true);
}
void displayDuplicateRows(bool matrix[][MAX], int M, int N) {
Trie* head = getNode();
for (int i = 0; i < M; i++)
if (!insert(head, matrix[i], N))
cout << "There is a duplicate row at position: "<< 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},
};
displayDuplicateRows(mat, 6, 6);
}
আউটপুট
There is a duplicate row at position: 3 There is a duplicate row at position: 4 There is a duplicate row at position: 5
