There are many conventional algorithms to solve this problem… like KMP. Is there any algo which is better than kmp?
Do codechef have any problem regarding string pattern matching for big sequences (like 10^6 characters)?
Can someone suggest me such problem on codechef?
i found one…but it is on SPOJ…LINK…i’ll add if i find more…
this is also a spoj problem…LINK
found another spoj problem…LINK…soultions to this problem are available on the internet…one such solution…LINK
thanks bro … also suggest me problems on codechef… i want to see how others have approached …
will try to find some…
A suffix tree is better if you will have to answer a lot of queries such as “is the needle present in the haystack?”. KMP is better if you only have to search for one string in another single string, and not have to do it a lot of times.
A suffix tree is a much more general data structure, so you can do a lot more with it. KMP is useful for finding if a string is a substring in another string.
You might also want to check out other algorithms, such as Boyer-Moore, Rabin-Karp and even the naive algorithm, as there are situations (inputs) in which one is better than the others.
Bottom line is:
If you have a lot of queries like the one I mentioned above, it’s worth to build a suffix tree and then answer each query faster.
If you need to do more than those kinds of queries, a suffix tree is also worth building.
If you only care about occasionally finding if a string is a substring of another string, then use KMP.
check this problem of spoj http://www.spoj.com/problems/SUB_PROB/
using KMP you will get TLE while using suffix tree you will get AC enjoy 