一个字符串算法的优化
题目如下：一个如acdnddnddndkjjjjlilili的字符串，转化为这样的形式ac dnd*3 k j*4 li*3
我目前用的方法是hash+回溯，如果字符串不长的话，还可以，比较长的话，效率就会很低。
不知道大家有什么好的办法没有 huffman编码 可以吗？ 匹配长度有无限制？
感觉楼上理解错意思了^^
不是要编码压缩，而是转换 to：gxqcn
感觉huffman有些问题，我觉得用后缀树似乎可以，但没有想清楚。
to：nlrte13
匹配长度无限制。 无限长保持高效很困难，RK算法已经不错啦。不过用在你这里要构造阶梯哈希表，随着长度增长，效率无限下降…… 我觉得只要先用hash表找到两个连续字母相同的位置,这个直接可以淘汰大部分情况.然后继续判断更大范围就可以了. 规则不太明白，是不是这样？
aaabbbaaabbb ->(a*3b*3)*2
一层层的做比较好，即先扫描1位长重复的，然后2位长 。。。。 这样n常的字符串要扫描n/2遍
第k次维护一个k长的FIFO。 对，要的就是这样的效果，呵呵，不过这样逐个比较的话，效率会比较低。
另外还要确保aaaaaa => a*6，而不是a*2*3 或 a*3*2
规则不太明白，是不是这样？
aaabbbaaabbb ->(a*3b*3)*2
一层层的做比较好，即先扫描1位长重复的，然后2位长 。。。。 这样n常的字符串要扫描n/2遍
第k次维护一个k长的FIFO。
shshsh_0510 发表于 2009-6-24 12:56 http://bbs.emath.ac.cn/images/common/back.gif 目前用的方法，和这个方法类似，不过在执行效率上，感觉还能够提高。
我觉得只要先用hash表找到两个连续字母相同的位置,这个直接可以淘汰大部分情况.然后继续判断更大范围就可以了.
mathe 发表于 2009-6-24 12:43 http://bbs.emath.ac.cn/images/common/back.gif 先扫描1位长的有时候会有问题，比如：
dvddvddvddvd
就会变为d(vd*2)*3vd 而不是dvd *4
规则不太明白，是不是这样？
aaabbbaaabbb ->(a*3b*3)*2
一层层的做比较好，即先扫描1位长重复的，然后2位长 。。。。 这样n常的字符串要扫描n/2遍
第k次维护一个k长的FIFO。
shshsh_0510 发表于 2009-6-24 12:56 http://bbs.emath.ac.cn/images/common/back.gif
页:
[1]
2