ব্যাড ক্যারেক্টার হিউরিস্টিক বয়ার মূর অ্যালগরিদমের একটি অন্য অ্যাপ্রোচ। এতে "ব্যাড ক্যারেক্টার" (যে ক্যারেক্টার মিসম্যাচ হয়) খুঁজে বের করা হয়। মিসম্যাচ হলে পুরো প্যাটার্ন শিফট করা হয় যাতে মিসম্যাচ ম্যাচে পরিণত হয়, নাহলে প্যাটার্ন ব্যাড ক্যারেক্টারকে পেরিয়ে চলে যায়।
কমপ্লেক্সিটি
- বেস্ট কেস: O(m/n)
- ওয়ার্স্ট কেস: O(mn) (m = প্যাটার্ন লেথ, n = টেক্সট লেথ)
ইনপুট এবং আউটপুট
Input: Main String: "ABAAABCDBBABCDDEBCABC", Pattern: "ABC"
Output: Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18
অ্যালগরিদম
badCharacterHeuristic(pattern, badCharArray)
Begin
n := pattern length
badCharArray সব এন্ট্রি -1 করে ইনিশিয়ালাইজ
for pattern-এর সব ক্যারেক্টার: badCharArray[char] = last position
End
searchPattern(pattern, text)
Begin
patLen, strLen
badCharacterHeuristic কল করুন
shift := 0
while shift <= strLen - patLen:
j := patLen - 1
while j >= 0 AND pattern[j] == text[shift+j]: j--
if j < 0: print match at shift
if shift+patLen < strLen: shift += patLen - badCharArray[text[shift+patLen]]
else: shift++
else: shift += max(1, j - badCharArray[text[shift+j]])
done
End
C++ উদাহরণ
#include <iostream>
#define MAXCHAR 256
using namespace std;
int maximum(int a, int b) { return (a>b)?a:b; }
void badCharacterHeuristic(string pattern, int badChar[MAXCHAR]) {
int n = pattern.size();
for(int i=0; i= 0 && pattern[j] == mainString[shift+j]) j--;
if(j < 0) {
(*index)++; array[*index] = shift;
if(shift + patLen < strLen) shift += patLen - badChar[mainString[shift+patLen]];
else shift++;
} else shift += maximum(1, j - badChar[mainString[shift+j]]);
}
}
int main() {
string mainString = "ABAAABCDBBABCDDEBCABC";
string pattern = "ABC";
int locArray[mainString.size()], index = -1;
searchPattern(mainString, pattern, locArray, &index);
for(int i=0; i<=index; i++) cout << "Pattern found at position: " << locArray[i] << endl;
}
আউটপুট
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18
