Algorithm For String Matching

Rocky · Post by **Rocky** » Thu May 26, 2005 7:59 am

What Is The Effiecient Algorithm For String Matching Then KMP.
Help Please.......

THANK"S IN ADVANCE
ROCKY

sumankar · Post by **sumankar** » Thu May 26, 2005 8:48 am

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.

nibbler · Post by **nibbler** » Thu May 26, 2005 12:03 pm

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?

Rocky · Post by **Rocky** » Tue May 31, 2005 8:06 am

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.

sumankar · Post by **sumankar** » Tue May 31, 2005 8:57 am

http://online-judge.uva.es/board/viewto ... 2&start=15
Adrian's post should give you all the hint you want.

Rocky · Post by **Rocky** » Tue May 31, 2005 12:45 pm

Thank'ssss...
Yes I Think It Will Help Me .

Thank's Again
Rocky