|
|
вернуться в форумAlgorithm how to solve this problem? construct suffix tree for N times and then LCP or there is easier and faster way? Re: Algorithm Construct suffix tree for each window. Sliding should be at most O(k). Re: Algorithm Try DP. It's easier to code (+ short) and run much faster than using suffix tree although having the same complexity O(N*K). Re: Algorithm Could you please decribe me DP solution? Re: Algorithm Stupid implementation of the hash-table is even easier to code and much easier to invent. Re: Algorithm Coding is not difficult at all. It seems to be more interesting that there exists O(n + k) solution, isn't it? Re: Algorithm O(n=4000 + k=1000) would work 0.001ms ;) Re: Algorithm Hardly. O(n + k) may have arbitrary coefficient. And no one said that solution had been submitted at Timus. Re: Algorithm Послано maksay 19 июн 2009 22:27 AC in 0.109 using only Z-function (also called suffix-function) Re: Algorithm Z-function is not necessary here, KMP is enough. 0.14 using KMP. Re: Algorithm And what is the "stupid implementation of the hash-table"? My stupid implementation got TL. Re: Algorithm Could you explain how to use KMP here? Re: Algorithm Edited by author 22.02.2014 15:24 Re: Algorithm Probably DP solution is actually a suffix automation. In suffix automation, we have the following DP. Let X is some state of DAWG. Let DP[X] =1+sum(DP[Y]){there is an edge from X to Y in DAWG}. Then the answer is DP [ROOT] - 1. (Because empty substring not counts) Edited by author 12.07.2017 12:20 |
|
|