问一个简单问题的算法# Computation - 科学计算
c*r
1 楼
给定一个字母序列,我想找到其中有多少重复的连续子序列,并且得到最长的重复序列
。比如序列
A L K S D E A E A R K S D E A E
可以看出重复序列很多,比如K S D ,K S D E等等,但K S D E A E重复了两遍,它是
重复序列里面最长的,我的目的就是得到它,并且得知它重复了两遍。
OK,最容易想到的方法大概是设置窗口扫描。比如我先取前三个字母ALK,然后在整条
序列里面扫描有没有重复的;如果没有,右移一位,扫描LKS;如果有,则给ALK延长一
位,扫描ALKS。。。重复以上过程,就能得到我想要的最长重复子序列。
我觉得可能有更有效率的方法,但一时想不出,恳请诸位如有好的想法,不吝指教,谢
谢。
。比如序列
A L K S D E A E A R K S D E A E
可以看出重复序列很多,比如K S D ,K S D E等等,但K S D E A E重复了两遍,它是
重复序列里面最长的,我的目的就是得到它,并且得知它重复了两遍。
OK,最容易想到的方法大概是设置窗口扫描。比如我先取前三个字母ALK,然后在整条
序列里面扫描有没有重复的;如果没有,右移一位,扫描LKS;如果有,则给ALK延长一
位,扫描ALKS。。。重复以上过程,就能得到我想要的最长重复子序列。
我觉得可能有更有效率的方法,但一时想不出,恳请诸位如有好的想法,不吝指教,谢
谢。