一个字符串算法的优化

litaoye

题目如下：一个如acdnddnddndkjjjjlilili的字符串，转化为这样的形式 ac dnd*3 k j*4 li*3 我目前用的方法是hash+回溯，如果字符串不长的话，还可以，比较长的话，效率就会很低。 不知道大家有什么好的办法没有

gxqcn

huffman编码 可以吗？

nlrte13

匹配长度有无限制？ 感觉楼上理解错意思了^^ 不是要编码压缩，而是转换

litaoye

to：gxqcn 感觉huffman有些问题，我觉得用后缀树似乎可以，但没有想清楚。 to：nlrte13 匹配长度无限制。

nlrte13

无限长保持高效很困难，RK算法已经不错啦。不过用在你这里要构造阶梯哈希表，随着长度增长，效率无限下降……

mathe

我觉得只要先用hash表找到两个连续字母相同的位置,这个直接可以淘汰大部分情况.然后继续判断更大范围就可以了.

shshsh_0510

规则不太明白，是不是这样？ aaabbbaaabbb ->(a*3b*3)*2 一层层的做比较好，即先扫描1位长重复的，然后2位长 。。。。 这样n常的字符串要扫描n/2遍 第k次维护一个k长的FIFO。

litaoye

对，要的就是这样的效果，呵呵，不过这样逐个比较的话，效率会比较低。 另外还要确保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

litaoye

目前用的方法，和这个方法类似，不过在执行效率上，感觉还能够提高。

我觉得只要先用hash表找到两个连续字母相同的位置,这个直接可以淘汰大部分情况.然后继续判断更大范围就可以了. mathe 发表于 2009-6-24 12:43

litaoye

先扫描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