ধরুন আমরা নিচের মত স্ট্রিমচেকার ক্লাস বাস্তবায়ন করতে চাই −
-
স্ট্রিমচেকার(শব্দ) - এটি হল কনস্ট্রাক্টর, এটি প্রদত্ত শব্দগুলির সাথে ডেটা স্ট্রাকচার শুরু করে৷
-
ক্যোয়ারী(অক্ষর) - এটি সত্য হয় যখন কিছু 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