求助：两个字符串首尾相接程序，重复区域不是完全重复,需要c++编程

penggongxin 发布于 2012-07-10 19:38， 975 次点击

举个简单的例子：
s1:"TTACCGTAAATACACCAACCAGTGACGTCAATTACTAGTGGATCACGCTTCCT"
和
s2:"TACTTGTGGAACACGCGTCCTTCTTTCCGTCTATGGACGGGGGTCCTTGTGCG"
需要输出的是：通过对s1和s2匹配判断（也可以直接考虑s1的末尾和s2的首部，取等长做匹配），在s1和s2的比较判断中，通过计算相对应字符的个数占整个匹配长度的比，取最大，去重复得到 TTACCGTAAATACACCAACCAGTGACGTCAATTACTAGTGGATCACGCTTCCTTCTTTCCGTCTATGGACGGGGGTCCTTGTGCG
(很明显，例子中的重复区域可以确定为TACTAGTGGATCACGCTTCCT，尽管有三个字符不相同)，问问各位大牛，C++程序怎么写！谢谢

5 回复

诸葛修勤2012-07-10 19:45

TTACCGTAAATACACCAACCAGTGACGTCAATTACTAGTGGATCACGCTTCCTT                     CTTTCCGTCTATGGACGGGGGTCCTTGTGCG
TTACCGTAAATACACCAACCAGTGACGTCAATTACTAGTGGATCACGCTTCCTT                     CTTTCCGTCTATGGACGGGGGTCCTTGTGCG
                                                                                     ACTTGTGGAACACGCGTCCTT

那和那儿是重复的？

penggongxin2012-07-10 19:48

回复 2楼诸葛修勤

就是S1的末尾和s2中间有个重复区域，但是不是完全重复区域

rjsp2012-07-11 12:00

通过计算相对应字符的个数占整个匹配长度的比，取最大，
------ 明显不通，如果这样，那就应该是“T”，因为此时“相对应字符的个数占整个匹配长度的比”为1，是最大的

penggongxin2012-07-11 18:41

回复 4楼 rjsp

对，你提的问题很对，可是这个现象怎么克服，是不是还有其他的参考标准。或者有其它的算法？

penggongxin2012-07-11 18:43

回复 4楼 rjsp

或者增加个规则，连续匹配字符要尽量多！