Sunday, August 23, 2009

KMP, Boyce moor and brute force

I was revising my concept on these algorithm....
Once i was master of algo but after staying out of touch lately, i feel my algorithm skills have gone blunt....
here i jump back...
KMP:
Practical Use: In reading data from network streams and large files...
More fruitful when alphabates are small...
It is claimed to be faster if mismatch occurs later in the series...
Prefix-suffix approach. Each alphabate of pattern to be searched is just traversed once.

Boyce moor:
Practical Use: Faster when alphabates are large and slow when alphabates are small...
Back-traversal based appraoch.

Brute force:
Practical Use: Poor for binary usage...
just O(n*m) solution...

Rabin carp:
Practical Use: Hashing function based approach...
Efficiency depends on hash functions quality...

No comments:

Post a Comment