Can this word search algorithm be made faster?

Posted by Ashwin Singh on Programmers See other posts from Programmers or by Ashwin Singh
Published on 2014-08-21T17:31:59Z Indexed on 2014/08/21 22:26 UTC
Read the original article Hit count: 309

Filed under:
|

Problem: Find a match of word S in text T

Given: S and T are part of spoken and written English.

Example: Match 'Math' in 'I love Mathematics'

NOTE: Ignore CASES.

My algorithm:

STEP 1) Convert S, T to char[]

STEP 2) for i=0, i < T.length , i++

STEP 3) for j=S.length-1, j>0 , j--

STEP 3 is the magic, instead of going about matching M,A,T,H, this matches M, H, T and finally A. This helps in eliminating a lot of possible partial matches. For example, if I go sequentially like M A as in Boyer Moore's method ... it can match Matter, Mass, Matchstick etc. using M _ _ H will bring down size of partial matches.

STEP 4) if S[j]!=T[i] -> break;
        else if j==i -> PRINT MATCH

© Programmers or respective owner

Related posts about algorithms

Related posts about search