一个字符串算法的优化

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