खराब चरित्र अनुमानी

बुरा चरित्र अनुमानी पद्धति बॉयर मूर एल्गोरिथम के दृष्टिकोणों में से एक है। एक अन्य दृष्टिकोण अच्छा प्रत्यय अनुमानी है। इस पद्धति में हम एक खराब चरित्र को खोजने की कोशिश करेंगे, जिसका अर्थ है कि मुख्य स्ट्रिंग का एक चरित्र, जो पैटर्न से मेल नहीं खाता है। जब बेमेल हो गया है, तब तक हम पूरे पैटर्न को तब तक शिफ्ट करेंगे जब तक कि बेमेल मेल न बन जाए, अन्यथा, पैटर्न खराब चरित्र से आगे निकल जाता है।

यहाँ समय जटिलता सर्वोत्तम स्थिति के लिए O(m/n) है और सबसे खराब स्थिति के लिए O(mn) है, जहाँ n पाठ की लंबाई है और m पैटर्न की लंबाई है।

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

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

एल्गोरिदम

badCharacterHeuristic(pattern, badCharacterArray)

>इनपुट - पैटर्न, जिसे खोजा जाएगा, स्थान को संग्रहीत करने के लिए खराब वर्ण सरणी

आउटपुट: भविष्य में उपयोग के लिए खराब वर्ण सरणी भरें

शुरुआत n:=badCharacterArray की सभी प्रविष्टियों के लिए पैटर्न की लंबाई, पैटर्न के सभी वर्णों के लिए सभी प्रविष्टियों को -1 पर सेट करें, badCharacterArray में प्रत्येक वर्ण की अंतिम स्थिति निर्धारित करें। किया समाप्त

खोज पैटर्न (पैटर्न, टेक्स्ट)

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

>आउटपुट - वे स्थान जहाँ पैटर्न पाया जाता है

पेटलेन शुरू करें:=पैटर्न की लंबाई strLen:=टेक्स्ट की लंबाई। कॉल badCharacterHeuristic(pattern, badCharacterArray) shift :=0 जबकि शिफ्ट <=(strLen - patLen), do j :=patLen -1 जबकि j>=0 और pattern[j] =text[shift + j], j को घटाएं 1 किया गया अगर j <0, तो शिफ्ट को प्रिंट करें, अगर शिफ्ट + पेटलेन <स्ट्रेलेन है, तो एक मैच है:=शिफ्ट + पेटलेन - बैड कैरेक्टरएरे [टेक्स्ट [शिफ्ट + पेटलेन]] और 1 और शिफ्ट द्वारा इंक्रीमेंट शिफ्ट:=शिफ्ट + मैक्स(1, j-badCharacterArray[text[shift+j]]) किया गयाअंत

उदाहरण

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