查找列表最长无重叠重复序列的算法优化及OCaml实现咨询

规则示例 #

[i;i;i;a;b;b;a;i;i;c] 
(* 最长重复序列为 [i;i] *)
[i;i;i;i] 
(* 此处最长模式为 [i;i]，要求序列重复且无重叠 *)

[t;f;f;t] 
(* 此处最长重复序列为 [t]，t是列表中第一个存在重复模式的元素 *)

现有设计思路 #

• 取列表当前遍历到的元素，将列表拆分为两部分：list_one为该元素左侧的所有元素，list_two为该元素右侧的所有元素。
• 检查该元素在list_one或list_two中是否存在匹配。
• 若存在匹配，将当前最长序列设为该元素。
• 将原列表中当前元素右侧的下一个元素拼接到当前序列后，再次检查新序列在list_one和list_two中是否存在匹配。
• 当拼接后的序列长度大于列表总长度/2时，停止当前轮次的检查。
• 以列表的下一个元素为起点，重复上述步骤，直到遍历完列表所有元素。

运行示例 #

[t;f;f;t]
(* 第一轮 *)
[t][][f;f;t]
(* 最后一个元素存在匹配 *)
current_max = [t]
(* 第二轮 *)
[t;f][][f;t]
(* 后续无匹配结果 *)
(* 切换到下一个元素，重新拆分列表，按上述步骤执行 *)
[f][t][f;t]
(* f存在匹配 *)
(* 后续流程重复...*) 

待确认问题 #

• 上述设计的算法是否存在缺陷？
• 是否有更简便的实现方案？
• 最终需要使用OCaml语言完成该功能开发。

内容的提问来源于stack exchange，提问作者linuxxx