s**x
发帖数: 7506 | 1 给一字典，求所能组成的最长的回文串，每个词最多用一次。 |
M*******a
发帖数: 1633 | |
c******0
发帖数: 260 | 3 我觉得这题很复杂啊。字典的单词应该是有序的。
应该只要建 reversed words 的trie就行了，然后遍历字典，看能不能找到一样的。
for(string str : dict){
check str 或者 str.substr(1) 是不是在 trie:
if yes, delete str in trie
else insert reversed str into trie;
}
【在 s**x 的大作中提到】
: 给一字典，求所能组成的最长的回文串，每个词最多用一次。
|
s**x
发帖数: 7506 | 4 这是非死不可的。 当时没做出来， 要求 hint. 说是 use trie, 从两头构造。
别的题目都是常见题。
大家以后多打汉字阿。 |
n********e
发帖数: 41 | 5 好难啊。两头构造怎么构？
http://norvig.com/palindrome.html
貌似有人专门搞这个 都算到
74,633 letters 了
【在 s**x 的大作中提到】
: 这是非死不可的。 当时没做出来， 要求 hint. 说是 use trie, 从两头构造。
: 别的题目都是常见题。
: 大家以后多打汉字阿。
|
W**********i
发帖数: 136 | 6 Google到的：
Constructing a longest palindrome using words in an online dictionary is a
question in an international online programming contest 2 years back (
Actually it is IOPC conducted by IIT Kanpur,India)...
【在 s**x 的大作中提到】
: 给一字典，求所能组成的最长的回文串，每个词最多用一次。
|
s******6
发帖数: 12 | 7
不是说一个词只能用一次吗，a 用了多少次了。。。
【在 n********e 的大作中提到】
: 好难啊。两头构造怎么构？
: http://norvig.com/palindrome.html
: 貌似有人专门搞这个 都算到
: 74,633 letters 了
|
g******n
发帖数: 10 | 8 是不是NPHard的？感觉可以构造一个worst case，规约到01背包。
比如一个词是n个a后面跟1个b，剩下的词数量很多，都只包含a但长度很短，且总长度
小于第一个词的两倍，且大于第一个词的长度。
没严格证明，不知道对不对。 |
s**x
发帖数: 7506 | 9 假设最左边单词是 dog，最右边肯定要以 god结束，要是把单词reverse 串建trie, 可
找到单词 abcgod,
有了abcgod, 左边又可以找到cbaxyz, 右边再找 ...zyx
we will have dogcbaxyz...zyxabcgod
差不多就这样，很巧妙。 |
c******0
发帖数: 260 | 10 但是你怎么找到abcgod呢？ 如果用trie， 那么你需要把整个trie都扫一遍啊。
要是找某个pattern是否在某个string里，应该用suffix tree
【在 s**x 的大作中提到】
: 假设最左边单词是 dog，最右边肯定要以 god结束，要是把单词reverse 串建trie, 可
: 找到单词 abcgod,
: 有了abcgod, 左边又可以找到cbaxyz, 右边再找 ...zyx
: we will have dogcbaxyz...zyxabcgod
: 差不多就这样，很巧妙。
|
