কম্পিউটার

C++ এ অক্ষরের স্ট্রীম


ধরুন আমরা নিচের মত স্ট্রিমচেকার ক্লাস বাস্তবায়ন করতে চাই −

  • স্ট্রিমচেকার(শব্দ) - এটি হল কনস্ট্রাক্টর, এটি প্রদত্ত শব্দগুলির সাথে ডেটা স্ট্রাকচার শুরু করে৷

  • ক্যোয়ারী(অক্ষর) - এটি সত্য হয় যখন কিছু k>=1 এর জন্য, শেষ k অক্ষরগুলি জিজ্ঞাসা করা হয় (প্রাচীন থেকে নতুন পর্যন্ত, এই চিঠিটি এইমাত্র জিজ্ঞাসা করা সহ) প্রদত্ত তালিকার একটি শব্দের বানান করে৷

সুতরাং, যদি ইনপুটটি শব্দ তালিকা =["ce", "g", "lm"] এর মত হয়, তাহলে [a,b,c,e,f,g,h,i,j,k'-এর জন্য বহুবার কল করুন ,l,m], তাহলে আউটপুট e, g, m এর জন্য সত্য হবে এবং অন্যদের জন্য মিথ্যা হবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

  • একটি নোড গঠন সংজ্ঞায়িত করুন, এখানে 26টি নোডের একটি অ্যারে রয়েছে এবং শেষ পতাকা রয়েছে

  • প্রাথমিকভাবে isEnd মিথ্যা, এবং চাইল্ড অ্যারে নাল দিয়ে পূর্ণ।

  • একটি নোড হেড সংজ্ঞায়িত করুন

  • নোডের একটি অ্যারে তৈরি করুন অপেক্ষা তালিকা

  • একটি ফাংশন সংজ্ঞায়িত করুন insertNode(), এটি হেড, s,

    লাগবে
    • curr :=মাথা

    • আরম্ভ করার জন্য i :=0, যখন i

      • x :=s[i]

      • যদি curr-এর সন্তান [x - 'a'] না হয়, তাহলে −

        • curr.child[x - 'a'] =একটি নতুন নোড নোড তৈরি করুন

      • curr :=curr.child[x - 'a']

    • curr এর শেষ :=সত্য

  • ইনিশিয়ালাইজার থেকে এটি করুন

    • head :=একটি নতুন নোড তৈরি করুন

    • আরম্ভ করার জন্য i :=0, যখন i <শব্দের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −

      • insertNode(head, words[i])

    • curr :=মাথা

  • একটি ফাংশন ক্যোয়ারী সংজ্ঞায়িত করুন(), এটি x,

    লাগবে
    • নোড টেম্পের একটি অ্যারে তৈরি করুন

    • যদি head.child[x - 'a'] হয়, তাহলে −

      • অপেক্ষা তালিকার শেষে মাথা ঢোকান

    • ret :=মিথ্যা

    • আরম্ভ করার জন্য i :=0, যখন i <অপেক্ষা তালিকার আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −

      • curr :=অপেক্ষা তালিকা[i]

      • যদি curr.child[x - 'a'], তাহলে

        • curr :=শিশু [x - 'a'] curr

        • টেম্পের শেষে curr ঢোকান

        • ret :=ret OR isEnd of curr

    • swap(temp, waitlist)

    • রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
struct Node {
   Node* child[26];
   bool isEnd;
   Node(){
      isEnd = false;
      for (int i = 0; i < 26; i++)
      child[i] = NULL;
   }
};
class StreamChecker {
   public:
   Node* head;
   vector<Node*> waitList;
   void insertNode(Node* head, string& s){
      Node* curr = head;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         if (!curr->child[x - 'a']) {
            curr->child[x - 'a'] = new Node();
         }
         curr = curr->child[x - 'a'];
      }
      curr->isEnd = true;
   }
   StreamChecker(vector<string>& words){
      head = new Node();
      for (int i = 0; i < words.size(); i++) {
         insertNode(head, words[i]);
      }
      Node* curr = head;
   }
   bool query(char x){
      vector<Node*> temp;
      if (head->child[x - 'a']) {
         waitList.push_back(head);
      }
      bool ret = false;
      for (int i = 0; i < waitList.size(); i++) {
         Node* curr = waitList[i];
         if (curr->child[x - 'a']) {
            curr = curr->child[x - 'a'];
            temp.push_back(curr);
            ret |= curr->isEnd;
         }
      }
      swap(temp, waitList);
      return ret;
   }
};
main(){
   vector<string> v = {"ce","g","lm"};
   StreamChecker ob(v);
   cout << (ob.query('a')) << endl;
   cout << (ob.query('b')) << endl;
   cout << (ob.query('c')) << endl;
   cout << (ob.query('e')) << endl;
   cout << (ob.query('f')) << endl;
   cout << (ob.query('g')) << endl;
   cout << (ob.query('h')) << endl;
   cout << (ob.query('i')) << endl;
   cout << (ob.query('j')) << endl;
   cout << (ob.query('k')) << endl;
   cout << (ob.query('l')) << endl;
   cout << (ob.query('m'));
}

ইনপুট

"ce","g","lm", query(),

আউটপুট

0 0 0 1 0 1 0 0 0 0 0 1

  1. C++ এ সবচেয়ে বড় BST সাবট্রি

  2. C++ স্ট্রীম ক্লাস স্ট্রাকচার

  3. C++ এ স্ট্রিংস্ট্রিম

  4. C++ এ ট্রিগ্রাফ