|
|
back to boardShow all messages Hide all messagesThere many ways: 1) hash 2) suffix array 3) suffix tree 4) suffix automation 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 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 |
|
|