|
|
back to boardWhat can I use the KMP algorithm for ? Posted by Dilyan 1 May 2005 00:16 not only in this problem. what can i use the KMP algorithm for? what kind of problems can i solve? I solved no problems using exactly KMP, but... (+) You can try to solve Ural-1269. The problem is very difficult, use Aho-Corasik algo which is a modification of KMP for several substrings. And there are several problems I solved via finite automatons, in some of them you can use KMP. As for this very problem (Ural-1354) - O(N^2) solution is OK :) Re: I solved no problems using exactly KMP, but... (+) I'd like to know the solution to 1269. I use something I'd call trie-graph, and it works very well for 1158, but it takes up too much memory. Could you teach me the modified version of the KMP algo, or give me a link? KMP is unnecessary here. Posted by SPIRiT 28 Aug 2006 12:50 As Dmitry Kovalioff stated before, O(N^2) solution works just fine. I found out empirically that 16 millions of operations fit just fine in one second. By the way, what was the jury idea? Was it really a trap task (seems hard with prefix functions, but quite simple with a little DP)? Or it's simply the time limit turned out to be too big? |
|
|
