Question

Give 3 Pattern/String Matching algorithms. Given a Text and a Pattern, apply the Boyer-Moore algorithm, The KMP algorithm, The Brute Force algorithm and match the pattern in the below string. Also, write the algorithm.

Text: CBADBCACBADCBBACACBCAABCA

Pattern: ACBCAABC

Answer the entire question Step by Step written out not typed. Don't answer if your answering part of question, typing solution, or guessing it.

Answer 1

Boyer Moore algorithm also preprocesses the pattern like KMP and Finite Automata algorithms.

Boyer Moore(B.M) is a combination of following two approaches.
1) Bad Character Heuristic

• character of the text which doesn’t match with the current character of the pattern is called the Bad Character.
• Upon mismatch, we shift the pattern until –
  1) The mismatch becomes a match
  2) Pattern P move past the mismatched character.
• 
• In the above example, we got a mismatch at position 3. Here our mismatching character is “A”. Now we will search for last occurrence of “A” in pattern. We got “A” at position 1 in pattern (displayed in Blue) and this is the last occurrence of it. Now we will shift pattern 2 times so that “A” in pattern get aligned with “A” in text.
• 
• Here we have a mismatch at position 7. The mismatching character “C” does not exist in pattern before position 7 so we’ll shift pattern past to the position 7 and eventually in above example we have got a perfect match of pattern (displayed in Green). We are doing this because, “C” do not exist in pattern so at every shift before position 7 we will get mismatch and our search will be fruitless.

  In the following implementation, we preprocess the pattern and store the last occurrence of every possible character in an array of size equal to alphabet size. If the character is not present at all, then it may result in a shift by m (length of pattern). Therefore, the bad character heuristic takes time in the best case.

2) Good Suffix Heuristic

The B.M algorithm does preprocessing of pattern and creates different arrays for both heuristics it uses best of the two heuristics at every step. B.M start matching from last character of the pattern.

KMP algorithm is used to find a "Pattern" in a "Text". This algorithm campares character by character from left to right. But whenever a mismatch occurs, it uses a preprocessed table called "Prefix Table" to skip characters comparison while matching. Some times prefix table is also known as LPS Table. Here LPS stands for "Longest proper Prefix which is also Suffix".

Steps for Creating LPS Table (Prefix Table)

• Step 1 - Define a one dimensional array with the size equal to the length of the Pattern. (LPS[size])
• Step 2 - Define variables i & j. Set i = 0, j = 1 and LPS[0] = 0.
• Step 3 - Compare the characters at Pattern[i] and Pattern[j].
• Step 4 - If both are matched then set LPS[j] = i+1 and increment both i & j values by one. Goto to Step 3.
• Step 5 - If both are not matched then check the value of variable 'i'. If it is '0' then set LPS[j] = 0 and increment 'j' value by one, if it is not '0' then set i = LPS[i-1]. Goto Step 3.
• Step 6- Repeat above steps until all the values of LPS[] are filled.

>Brute Force

Naive Pattern Searching:
Slide the pattern over text one by one and check for a match. If a match is found, then slides by 1 again to check for subsequent matches.