सी ++ में बाइनरी मैट्रिक्स में डुप्लिकेट पंक्तियां खोजें

मान लीजिए कि हम एक बाइनरी मैट्रिक्स हैं। यहां हम देखेंगे कि उस मैट्रिक्स में डुप्लिकेट पंक्तियों को कैसे खोजा जाए। मान लीजिए मैट्रिक्स इस तरह है -

3, 4, 5 की स्थिति में डुप्लिकेट पंक्तियाँ हैं।

इसे हल करने के लिए, हम 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