Page 1 of 1
Algorithm For String Matching
Posted: Thu May 26, 2005 7:59 am
by Rocky
What Is The Effiecient Algorithm For String Matching Then KMP.
Help Please.......
THANK"S IN ADVANCE
ROCKY
Posted: Thu May 26, 2005 8:48 am
by sumankar
Depends on what problem are you trying to solve!
Its hard to tell, as performance of two algorithms depends on a lot of factors specially in case of string matching.Why don't you go read up on what we have here
http://www-igm.univ-mlv.fr/~lecroq/string/.Maybe, you will have a better idea and be able to judge yourself.
HTH
Suman.
Posted: Thu May 26, 2005 12:03 pm
by nibbler
KMP is O(N+M), which is worst case optimal. Boyer-Moore variants also have O(N+M) worst case, but their best case can be down to O(M+N/M), which is much better. If you are searching for more then one pattern, use Aho-Corasick. Is there a particular problem that you are trying to solve?
Posted: Tue May 31, 2005 8:06 am
by Rocky
Thank's For Reply.
Actually I Want To Solve The Problem 10679 (I LOVE STRING)
I Think KMP Is Not Enough For That Problem.Is It?????
Thank's Again
Rocky.
Posted: Tue May 31, 2005 8:57 am
by sumankar
Thank's For Reply
Posted: Tue May 31, 2005 12:45 pm
by Rocky
Thank'ssss...
Yes I Think It Will Help Me .
Thank's Again
Rocky