Re: I got MLE, TLE on test #9, WA on test #8 :( No tricks, I have almost double reserve in memory. But I use hash working with edges, may be that's the matter. Yes, I got it Accepted at last :) The trick is to use your own hash implementation rather than hash_map from STL! Did anybody solve this problem using STL? Suffix Array seemed a lot faster in implementation I just got AC with Suffix Array + LCP in 0.3xx secs.
The implementation is cleaner than Suffix Tree and requires less space yet still run in O( N ) time.
I'm curious with Burunduk1's Suffix Automaton, is there any online resources available to learn about Suffix Automaton? I really want to solve this problem using Suffix Automaton :) Re: I got MLE, TLE on test #9, WA on test #8 :( What I did is to create 1 Suffix Tree with string: s1 + "$" + s2 + "#" where s1 and s2 is the first and second string in the input. After I built the Suffix Tree, I traversed it and find the deepest node which has child "$" and "#". this is exactly what iam trying to do but i got stack overflow in test case 9, obviously the stach overflows when i traverse the tree wishing to find the deepest node which has the two terminator characters as children (or in the subtree below). I guess the tree is too deep, so how could u solve this part? Re: I got MLE, TLE on test #9, WA on test #8 :( Don't traverse the tree using recursion ;)
Try using explicit array[100000] Re: I got MLE, TLE on test #9, WA on test #8 :( Don't traverse the tree using recursion ;)
Try using explicit array[100000] Do u mean to use that array to bottom up traverse the tree? or u mean something else? Re: I got MLE, TLE on test #9, WA on test #8 :( Don't traverse the tree using recursion ;)
Try using explicit array[100000] Do u mean to use that array to bottom up traverse the tree? or u mean something else? A recursion is using stack implicitly (stack memory) and it has limitation on the depth of the recursion for some compiler (or maybe by the stack memory configuration of the compiler). So, instead of using stack memory we can use an explicit stack array to simulate the same behavior. However, the code gets uglier and harder to read :p Update Suffix Tree gets AC in 0.14 time and 23 888 KB
Suffix Automation gets AC in 0.125 time and 22 320 KB
autor is me
P.S. Who can tell me, how to implement Suffix Array in O(n)? Re: Update Suffix array can be constructed in O(n) time by Karkkainen-Sanders algorithm. Re: I got TLE on #28, with single hash solution. Hi!
I have tried so many interpretations of the main idea for finding suffix array in O(NlogN), but all of them (except 1, because I optimize it) ran for more than 2 second .
Would you share the secret, I mean is there something special you do? Re: I got TLE on #28, with single hash solution. There is no any secret. Try to find original article "Faster Suffix sorting" by N.Jasper Larson and Kunihico Sadakane. Also very useful article for this problem is "Two Space Saving Tricks for Linear Time LCP array Computation" by Giovanni Manzini. Re: I got TLE on #28, with single hash solution. Thank's. Re: Update Hi WiNGeR, You might be interested to see this demo about creating Suffix Array in linear time by Juha Karkkainen and Peter Sanders: http://felix-halim.net/pg/suffix-array/index.php Do you have any reference on how to build Suffix Automaton? Which one is simpler? Suffix Tree or Automaton? Thanks Re: hashing i relalize double hashing, but i get tle on test 9.
Can anybody get me hash-functions used in solution on this problem? Re: hashing try 64bit hashing Re: hashing I can't use single hash to solve the problem...
Would you please tell me how to design the hash?
And what is the 64bit hashing meaning? Suffix Automata are simple As far as I am concerned, Suffix Automata are the best tool for solving this problem. At least, it holds for me. I got AC three hours after I started reading "Automata for Matching Patterns" ( http://www-igm.univ-mlv.fr/~mac/REC/B4.html ). Earlier I spent much more time on Suffix Trees and Arrays - and I failed to solve this problem by their means. Would be grateful for any hints concerning Trees and Arrays (just curious). Hints for impementingsuffix trees Posted by SPIRiT 7 Aug 2009 22:51 I used the standard ukkonen implementation. However, I use sibling lists for edges representation (watch Wikipedia "Suffix tree"), and I make leaves of tree explicit, that means that in the worst case you have 2*N nodes totally, N of them are leaves, where N is the total size of the text. This works fine.
Also, for the traversal of the tree, I used simple recursion. I tried to use stack modelling, as someone proposed in the posts earlier, but failed with TLE on test 9. In order not to get stack overflow set up the size of the stack about 10 megabytes (watch FAQ in order to learn, how to do it). nlogn I just did it with hash and my own hash table for 0.265 sec and 7mb memory. Re: Hints for impementingsuffix trees I used the standard ukkonen implementation. However, I use sibling lists for edges representation (watch Wikipedia "Suffix tree"), and I make leaves of tree explicit, that means that in the worst case you have 2*N nodes totally, N of them are leaves, where N is the total size of the text. This works fine.
Also, for the traversal of the tree, I used simple recursion. I tried to use stack modelling, as someone proposed in the posts earlier, but failed with TLE on test 9. In order not to get stack overflow set up the size of the stack about 10 megabytes (watch FAQ in order to learn, how to do it). Totaly agree. Sibling lists save memory well, and work pretty fast. I also needed to increase stack size. http://acm.timus.ru/status.aspx?author=48362&from=3761647&count=1 |
