बॉयर मूर एल्गोरिथम

यह बॉयर मूर एल्गोरिथम का एक और तरीका है। कभी-कभी इसे गुड प्रत्यय अनुमानी पद्धति कहा जाता है। इस स्थिति के लिए, प्रत्यय तालिका के रूप में एक प्रीप्रोसेसिंग तालिका बनाई जाती है। इस प्रक्रिया में, पैटर्न के अंतिम वर्ण से सबस्ट्रिंग या पैटर्न की खोज की जाती है। जब मुख्य स्ट्रिंग का एक सबस्ट्रिंग पैटर्न के सबस्ट्रिंग के साथ मेल खाता है, तो यह मिलान किए गए सबस्ट्रिंग की अन्य घटनाओं को खोजने के लिए आगे बढ़ता है। यह पैटर्न के उपसर्ग को खोजने के लिए भी आगे बढ़ सकता है जो मुख्य स्ट्रिंग का प्रत्यय है। अन्यथा, यह पैटर्न की पूरी लंबाई को हिला देता है।

इनपुट और आउटपुट

इनपुट:मुख्य स्ट्रिंग:"ABAAABCDBBABCDDEBCABC", पैटर्न:"एबीसी" आउटपुट:स्थिति पर पाया गया पैटर्न:स्थिति पर 4 पैटर्न मिला:स्थिति पर 10 पैटर्न मिला:18

एल्गोरिदम

fullSuffixMatch(shiftArray, BorderArray, पैटर्न)

इनपुट - शिफ्ट स्थानों, सीमा सरणी और खोज के पैटर्न को संग्रहीत करने के लिए सरणी।

आउटपुट - शिफ्ट ऐरे और बॉर्डर ऐरे को भरें।

शुरू करें n:=पैटर्न लंबाई j :=n j :=n+1 borderArray[i] :=j जबकि i> 0, do जबकि j <=n और पैटर्न[i-1] पैटर्न[j-1] , अगर शिफ्टअरे [जे] =0 करें, तो शिफ्टअरे [जे]:=जे-आई; जे:=सीमाअरे [जे]; किया गया i और j को 1 सीमा से घटानाअरे [i] :=j किया गयाअंत

आंशिक प्रत्यय मैच (शिफ्टअरे, बॉर्डरअरे, पैटर्न)

इनपुट- शिफ्ट स्थानों, सीमा सरणी और खोज के पैटर्न को संग्रहीत करने के लिए सरणी।

आउटपुट - शिफ्ट ऐरे और बॉर्डर ऐरे को भरें।

प्रारंभ n :=पैटर्न लंबाई j :=borderArray[0] पैटर्न के सभी वर्णों 'i' की अनुक्रमणिका के लिए, यदि ShiftArray[i] =0 करें, तो ShiftArray[i] :=j यदि i =j तो j करें :=सीमाअरे [j] किया गयाअंत

खोज पैटर्न (पाठ, पैटर्न)

इनपुट: मुख्य पाठ और पैटर्न, जिसे खोजा जाएगा

आउटपुट - इंडेक्स जहां पैटर्न पाया जाता है

पेटलेन शुरू करें:=पैटर्न लंबाई strLen:=शिफ्टअरे की सभी प्रविष्टियों के लिए टेक्स्ट आकार, सभी प्रविष्टियों को 0 पूर्ण कॉल पर सेट करें पूर्ण प्रत्यय मैच (शिफ्टअरे, सीमाअरे, पैटर्न) कॉल आंशिक प्रत्यय मैच (शिफ्टअरे, सीमाअरे, पैटर्न) शिफ्ट:=0 जबकि शिफ्ट <=(strLen - patLen), j करें:=patLen -1 जबकि j> =0 और पैटर्न [j] =टेक्स्ट [शिफ्ट + j], j को 1 से घटाएं यदि j <0 है, तो शिफ्ट को प्रिंट करें , एक मैच शिफ्ट है:=शिफ्ट + शिफ्टअरे [0] और शिफ्ट:=शिफ्ट + शिफ्टअरे [जे + 1] किया गया अंत 

उदाहरण

#शामिल करेंनेमस्पेस std का उपयोग करना;void fullSuffixMatch(int shiftArr[], int BorderArr[], string pattern) { int n =pattern.size (); // पैटर्न की लंबाई पाएं int i =n; इंट जे =एन+1; बॉर्डरएआर [i] =जे; जबकि (i> 0) {// सही खोजें जब (i-1)वें और (j-1)वें आइटम समान न हों जबकि (j <=n &&पैटर्न [i-1]! =पैटर्न [j-1] ) { अगर (शिफ्टएआर [जे] ==0) शिफ्टएआर [जे] =जे-आई; // i से j j पर शिफ्ट पैटर्न =BorderArr [j]; // अद्यतन सीमा } मैं--; जे--; बॉर्डरएआर [i] =जे; } }शून्य आंशिक प्रत्यय मैच (इंट शिफ्टएआर [], इंट बॉर्डरएआर [], स्ट्रिंग पैटर्न) {इंट एन =पैटर्न। आकार (); // पैटर्न की लंबाई खोजें int j; जे =बॉर्डरएआर [0]; for(int i =0; i =0 &&पैटर्न [जे] ==मेनस्ट्रिंग [शिफ्ट + जे]) {जे--; // j को कम करें जब पैटर्न और मुख्य स्ट्रिंग वर्ण मेल खा रहे हों } if(j <0) {(*index)++; सरणी [(* अनुक्रमणिका)] =शिफ्ट; शिफ्ट + =शिफ्टअरे [0]; } और {शिफ्ट + =शिफ्टअरे [जे + 1]; } }}इंट मेन () {स्ट्रिंग मेनस्ट्रिंग ="एबीएएएबीसीडीबीबीएबीसीडीडीईबीसीएबीसी"; स्ट्रिंग पैटर्न ="एबीसी"; int locArray [mainString.size ()]; इंट इंडेक्स =-1; सर्चपैटर्न (मेनस्ट्रिंग, पैटर्न, लोकअरे, और इंडेक्स); for(int i =0; i <=index; i++) { cout <<"पैटर्न स्थिति पर पाया गया:" < 
आउटपुट
 
पैटर्न स्थिति में मिला:4Pattern स्थिति पर मिला:10Pattern स्थिति में मिला:18