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: 305
algorithms
|search
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