আহো-কোরাসিক অ্যালগরিদম

এই অ্যালগরিদম সমস্ত প্রদত্ত কীওয়ার্ড সেটের সমস্ত ঘটনা খুঁজে পেতে সহায়ক৷ এটি এক ধরনের অভিধান-ম্যাচিং অ্যালগরিদম। এটি সমস্ত কীওয়ার্ড ব্যবহার করে একটি গাছের কাঠামো ব্যবহার করে। গাছ তৈরি করার পরে, এটি রৈখিক সময়ে অনুসন্ধান করতে গাছটিকে একটি অটোমেটন হিসাবে রূপান্তর করার চেষ্টা করে। আহো-কোরাসিক অ্যালগরিদমের তিনটি ভিন্ন পর্যায় রয়েছে।

এগুলি হল গো-টু, ব্যর্থতা,৷ এবং আউটপুট . গো-টু পর্যায়ে, এটি সমস্ত কীওয়ার্ড ব্যবহার করে গাছ তৈরি করে। পরবর্তী পর্যায়ে বা ব্যর্থতার পর্যায়ে, এটি কিছু কীওয়ার্ডের সঠিক প্রত্যয় পেতে পশ্চাদমুখী রূপান্তর খুঁজে বের করার চেষ্টা করে। আউটপুট পর্যায়ে, অটোমেটনের প্রতিটি স্টেট 's'-এর জন্য, এটি স্টেট 's'-এ শেষ হওয়া সমস্ত শব্দ খুঁজে পায়।

এই অ্যালগরিদমের সময় জটিলতা হল:O(N + L + Z), যেখানে N হল টেক্সটের দৈর্ঘ্য, L হল কীওয়ার্ডের দৈর্ঘ্য এবং Z হল অনেকগুলি মিল।

ইনপুট এবং আউটপুট

ইনপুট:প্যাটার্নের একটি সেট:{তাদের, সেখানে, উত্তর, কোনো, বাই} প্রধান স্ট্রিং:"isthereanyanswerokgoodbye" আউটপুট:Word there location:2 Word যেকোন অবস্থান:7Word উত্তরের অবস্থান:10Word bye location:22

অ্যালগরিদম

বিল্ড ট্রি(প্যাটার্নলিস্ট, সাইজ)

ইনপুট - সমস্ত প্যাটার্নের তালিকা এবং তালিকার আকার

আউটপুট - প্যাটার্নগুলি খুঁজতে রূপান্তর মানচিত্র তৈরি করুন

আউটপুট অ্যারের সমস্ত উপাদানকে 0-এ সেট করা শুরু করুন ব্যর্থ অ্যারের সমস্ত উপাদানকে -1 তে সেট করুন গোটো ম্যাট্রিক্সের সমস্ত উপাদানকে -1 অবস্থায় সেট করুন :=1 //প্রথমে শুধুমাত্র একটি অবস্থা আছে। প্যাটার্নলিস্টের সমস্ত প্যাটার্ন 'i'-এর জন্য, শব্দটি করুন :=patternList[i] present :=0 শব্দের সমস্ত অক্ষর 'ch'-এর জন্য, do if goto[present, ch] =-1 তারপর goto[present, ch] :==রাজ্যের অবস্থা :=রাষ্ট্র + 1 উপস্থিত:=goto[বর্তমান, ch] সম্পন্ন আউটপুট [প্রেজেন্ট] :=আউটপুট [প্রেজেন্ট] বা (i বারের জন্য 1 বাম স্থানান্তর) সব ধরনের অক্ষরের জন্য করা হয়েছে ch, do if goto[0 , ch] ≠ 0 তারপর fail[goto[0,ch]] :=0 insert goto[0, ch] একটি সারিতে q. q খালি না থাকা অবস্থায় করা হয়েছে, newState করুন :=q থেকে q এর প্রথম উপাদান মুছে দিন। সমস্ত সম্ভাব্য অক্ষরের জন্য ch, goto[newState, ch] ≠ -1 হলে ব্যর্থ হন :=ব্যর্থ[নতুন রাষ্ট্র] যখন goto[failure, ch] =-1, ব্যর্থ হন :=goto[failure, ch] সম্পন্ন ব্যর্থ[গোটো [newState, ch]] =ব্যর্থতার আউটপুট[goto[newState, ch]] :=output[goto[newState,ch]] অথবা output[failure] q এ goto[newState, ch] সন্নিবেশ করুন। সম্পন্ন হয়েছে রিটার্ন স্টেটএন্ড

getNextState(presentState, nextChar)

ইনপুট −৷ বর্তমান অবস্থা এবং পরবর্তী অক্ষর পরবর্তী অবস্থা নির্ধারণ করতে

আউটপুট : পরবর্তী অবস্থা

উত্তর শুরু করুন :=presentState ch :=nextChar while goto[answer, ch] =-41, do answer :=fail[answer] সম্পন্ন হয়েছে ফেরত যান [উত্তর, ch]শেষ

প্যাটার্ন সার্চ (প্যাটার্নলিস্ট, সাইজ, টেক্সট)

ইনপুট - প্যাটার্নের তালিকা, তালিকার আকার এবং প্রধান পাঠ্য

আউটপুট - পাঠ্যের সূচী যেখানে প্যাটার্ন পাওয়া যায়

Begin call buildTree(patternList, size) presentState :=0 পাঠ্যের সমস্ত সূচীগুলির জন্য, যদি আউটপুট [presentState] =0 পরবর্তী অংশ উপেক্ষা করে এবং প্যাটার্নলিস্টে সমস্ত প্যাটার্নের জন্য পরবর্তী পুনরাবৃত্তির জন্য যান, প্যাটার্ন পাওয়া গেলে তা করুন আউটপুট অ্যারে ব্যবহার করে, তারপর অবস্থানটি মুদ্রণ করুন যেখানে প্যাটার্ন উপস্থিত রয়েছে সম্পন্ন হয়েছে 
উদাহরণ
 
#include #include #define MAXS 500 //সমস্ত প্যাটার্নের দৈর্ঘ্যের যোগফল#MAXC 26 // বর্ণমালার নামস্থান std;int output[MAXS];int fail[MAXS-এ 26টি অক্ষর হিসাবে সংজ্ঞায়িত করুন ];int gotoMat[MAXS][MAXC];int buildTree(স্ট্রিং অ্যারে[], int সাইজ) { for(int i =0; i q; এর জন্য (int ch =0; ch  
আউটপুট
 
Word there location:2Word any location:7Word answer location:10Word bye location:22