c语言 DNA模拟问题

来源：百度知道 编辑：UC知道 时间：2024/06/22 02:17:43
编写一个高效的算法并用程序实现在一个模拟DNA基因密码字符长链中找出最长的相同码段的操作。
例如，假设输入一个字符码串“abcdabcefda”，则其最长的相同子串为“abc”，长度为3。你的程序执行完后要求输出以下结果：
3 （最长相同子串长度）
abc （最长的相同子串）

给定的模拟DNA基因密码字符长链存储于文件DNA_code.txt中。

尽量提高成效的效率......
要求c语言版的！字符长链的长度是百万数量级

后缀数组或者后缀树
如果你不知道这两个是什么东西，建议先去搜点资料来看看。。。除了这两个东西我没想到什么比较好的方法

用比较直观的后缀树为例，假设树中某一节点u对应的字符串为s，深度为d，以u为根的子树包含了k个叶子节点，那么在原先的字符串里面，就找到了一个长度为d的字符串s恰好出现了k次
后缀树建立可以用Ukkonen算法，建立以后把整棵树遍历一下就可以了
整个过程都是比较直观的，就是编码太麻烦
而且你要求用c语言，粗略估计大概300行以上

或者你用线性的算法生成一个后缀数组，然后比较相邻两个后缀的lcp，找出最大的那个就是了
后缀数组的线性时间构造貌似也是个比较复杂的东西

总之代码较长，内容比较专业，不建议你在这里问
最好自己去找找相关资料