String Algorithms :The BOYER-MOORE Algorithm

0
1894

Iterations at HiringLibrary-Com

 

One last algorithm we will be discussing for string search is the Boyer-Moore algorithm. The idea behind this approach is that it iterates through the bigger string from right to left. Consider the following example:

Find ababac in “abbdbeababacad”. We firstly align the strings as follows:

Missmatch at HiringLibrary-comabbdbeababacad

ababac

 

 

We compare ‘c’ with ‘e’. Since ‘e’ does not appear in the string we are searching for, so we know the match cannot occur for any of the positions 0, …, 5. Therefore we can move the smaller string 6 positions to the right, as follows:

Success as match occurs - HiringLibrary-Comabbdbeababacadc

ababac

 

 

Again, we compare ‘c’ with ‘c’, ‘a’ with ‘a’, and so on, until we notice that a matching has occurred. Next, we move one position to the right.

 

abbdbeababacadc

ababac

 

We compare ‘c’ with ‘a’ and, since a match does not occur, this means in theory we could move 5 positions to the right again. The algorithm stops here because this means we would exceed the capacity of the bigger string.

 

SHARE
Previous articleString Algorithms :The RABIN-KARP Algorithm
Next articleNon Deterministic Polynomial Or NP-Completeness Algorithms
Since last 15 years in different geographical locations, Sumit prepared hiring format for several hiring managers/teams to hire the balanced talents and interviewed talents on the various stages of their selection process. He also interviewed by hundreds of companies in different geographical locations.His best conclusion for hiring teams and candidate is to prepare in advance. Here ‘advance’ means keep your interview book ready and continue to update it even you are not going to interview candidates or applying for any job in next six months.