top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How does the Horspool’s algorithm work?

+1 vote
172 views
How does the Horspool’s algorithm work?
posted Apr 18, 2015 by Vrije Mani Upadhyay

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

Searching a large block of text to find the first occurrence of a substring (which we will call the ‘pattern’). This particular operation is provided in most text editing systems and it also has applications in bibliographic retrieval systems. Since the text tobe searched can be overwhelmingly large — perhaps hundreds of thousands of characters, itis important to use efficient techniques.

Boyer and Moore algorithm (Horspool)is a truly practical approach.
As in the Boyer-Moore algorithm, the pattern is compared from right to left with the text. After a complete match or in case of a mismatch, the pattern is shifted according to the precomputed function occ.

void horspoolSearch()
{
    int i=0, j;
    while (i<=n-m)
    {
        j=m-1;
        while (j>=0 && p[j]==t[i+j]) j--;
        if (j<0) report(i);
        i+=m-1;
        i-=occ[t[i]];
    }
}
answer Apr 18, 2015 by Amit Kumar Pandey
Similar Questions
0 votes

What UE does when UE is in idle mode ? How frequently ue look for paging and through which feature / algorithm ?

0 votes

In which scenarios networking namespace concept is used ?

...