|
|
back to boardHow to solve it? Need DP? Re: How to solve it? Need DP? There many ways: 1) hash 2) suffix array 3) suffix tree 4) suffix automation Re: How to solve it? Need DP? Thank you, I've got AC Re: How to solve it? Need DP? Posted by svr 15 Oct 2007 19:57 10000 suffices,graph of they. Suffix s1 connected with suffix s2 if exist word s, adjusting which to s1 we will have s2 as a rest. BFS in graph to find when rest will be equal empty:1) s=s1+s2; s=s3+s1+s4;s2=s1+s4. Ac at last with above approach. It imortant to right work with 20000. Edited by author 22.11.2008 14:52 Re: How to solve it? Need DP? Create characters tree for all words (allowing direct per-character steps at O(1) and enumeration of all children also at O(1)). DP over IxJ, I - word number, J - suffix length. Cover these suffixes with other words till length delta become zero. I used Dijkstra for that because length can change arbitrarily. Start in words which contain some other word as a prefix. Edited by author 20.08.2008 11:11 Re: How to solve it? Need DP? I used DP on trie. |
|
|