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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给一字典,求所能组成的最长的回文串,每个词最多用一次。
|
s**x 发帖数: 7506 | 4 这是非死不可的。 当时没做出来, 要求 hint. 说是 use trie, 从两头构造。
别的题目都是常见题。
大家以后多打汉字阿。 |
n********e 发帖数: 41 | 5 好难啊。两头构造怎么构?
http://norvig.com/palindrome.html
貌似有人专门搞这个 都算到
74,633 letters 了
【在 s**x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是非死不可的。 当时没做出来, 要求 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给一字典,求所能组成的最长的回文串,每个词最多用一次。
|
s******6 发帖数: 12 | 7
不是说一个词只能用一次吗,a 用了多少次了。。。
【在 n********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好难啊。两头构造怎么构? : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设最左边单词是 dog,最右边肯定要以 god结束,要是把单词reverse 串建trie, 可 : 找到单词 abcgod, : 有了abcgod, 左边又可以找到cbaxyz, 右边再找 ...zyx : we will have dogcbaxyz...zyxabcgod : 差不多就这样,很巧妙。
|