我该如何找到重复的单词序列
我需要检测只有标题的多个柱状数据块的存在。 除了标题词之外，没有其他任何关于数据的知识，标题词对于每组数据都是不同的。
重要的是，事先不知道每个块中有多少个字，因此，有多少个块。
同样重要的是，单词列表总是相对较短 – 小于20。
因此，给定一个标题或标题数组，例如：
Opt Object Type Opt Object Type Opt Object Type 什么是处理效率最高的方法来确定它完全由重复序列组成：
Opt Object Type
它必须是精确匹配，所以我的第一个想法是搜索[1+]寻找匹配到[0]，称它们为索引n，m，…然后如果它们是等距的检查[1] == [n + 1] == [m + 1]，[2] == [n + 2] == [m + 2]等。
编辑：它必须适用于单词集，其中一些单词本身在一个块内重复，所以
Opt Opt Object Opt Opt Object
是一套2
Opt Opt Object
如果列表由x个重复组组成，那么每个组包含n个元素……
我们知道至少有一组，所以我们将看看是否有2个重复组，通过比较列表的前半部分和后半部分进行测试。
1）如果上述情况属实，我们知道解决方案是2的因子
2）如果上述情况为假，我们将移动到下一个最大的素数，它可以被总字数整除……
在每个步骤中，我们检查列表之间的相等性，如果我们发现它，那么我们知道我们有一个解决方案。
我们想要返回一个单词列表，其中我们找到了第一个素数的最大因子，我们发现它们在子列表中是相等的。
因此，我们在子列表中应用上述公式，知道所有子列表都相等…因此，解决方案最好以递归方式求解。 那就是我们只需要孤立地考虑当前的子列表。
如果加载了一个简短的素数表，解决方案将非常有效……在此之后，有必要计算它们，但如果考虑到只有几十个质数的列表，则列表必须是非常简单的。
单位序列可以包含自己的重复吗？ 你知道单位序列的长度吗？
例如
ABCABCABCDEFABCABCABCDEFABCABCABCDEF
其中单位序列是ABCABCABCDEF
如果答案是肯定的，我认为你有一个难题，除非你知道单位序列的长度（在这种情况下解决方案是微不足道的，你只需要制作一个首先存储单位序列的状态机，然后validation序列的每个元素其余部分对应于单元序列的每个元素）。
如果答案为否，请使用此变体Floyd的循环查找算法来识别单位序列：
- 将指针P1和P2初始化到序列的开头。
- 对于每个新元素，每次递增指针P1，并每隔一段时间递增指针P2（保持计数器执行此操作）。
-
如果P1指向P2的相同元素，则表示您已找到单位序列。
-
现在重复序列的其余部分以validation它是否包含重复项。
更新：你已经澄清了你的问题，说明单位序列可能包含自己的重复。 在这种情况下，使用循环查找算法，但它只能保证找到潜在的循环。 使其在整个序列中保持运行，并使用以下状态机，从状态1开始：
状态1：没有发现有效的循环; 继续寻找。 当循环寻找算法找到潜在循环时，validation您是否从P获得了2个初步单元序列的副本，并转到状态2.如果到达输入的末尾，请转到状态4。
状态2：找到初步单元序列。 只要循环重复相同，就运行输入。 如果到达输入的末尾，请转到状态3.如果找到的输入元素与单位序列的相应元素不同，请返回到状态1。
状态3：如果输入的结尾包含单元序列的完全重复，则输入是单元序列的重复。 （如果它位于单元序列的中间，例如ABCABCABCABCAB则会找到一个单元序列，但它不包含完整的重复序列。）
状态4：未找到单元序列。
在我的例子中（重复ABCABCABCDEF ），算法首先找到ABCABC，它将把它置于状态2，并且它将保持在那里直到它击中第一个DEF，这会将其置于状态1，然后可能在两者之间来回跳转状态1和2，直到它到达第二个ABCABCABCDEF，此时它将重新进入状态2，并且在输入结束时它将处于状态3。
比我的另一个更好的答案：一个有效的Java实现，应该很容易理解，并且是通用的：
package com.example.algorithms; import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.List; interface Processor { public void process(T element); } public class RepeatingListFinder implements Processor { private List unit_sequence = new ArrayList (); private int repeat_count = 0; private int partial_matches = 0; private Iterator iterator = null; /* Class invariant: * * The sequence of elements passed through process() * can be expressed as the concatenation of * the unit_sequence repeated "repeat_count" times, * plus the first "element_matches" of the unit_sequence. * * The iterator points to the remaining elements of the unit_sequence, * or null if there have not been any elements processed yet. */ public void process(T element) { if (unit_sequence.isEmpty() || !iterator.next().equals(element)) { revise_unit_sequence(element); iterator = unit_sequence.iterator(); repeat_count = 1; partial_matches = 0; } else if (!iterator.hasNext()) { iterator = unit_sequence.iterator(); ++repeat_count; partial_matches = 0; } else { ++partial_matches; } } /* Unit sequence has changed. * Restructure and add the new non-matching element. */ private void revise_unit_sequence(T element) { if (repeat_count > 1 || partial_matches > 0) { List new_sequence = new ArrayList (); for (int i = 0; i < repeat_count; ++i) new_sequence.addAll(unit_sequence); new_sequence.addAll( unit_sequence.subList(0, partial_matches)); unit_sequence = new_sequence; } unit_sequence.add(element); } public List getUnitSequence() { return Collections.unmodifiableList(unit_sequence); } public int getRepeatCount() { return repeat_count; } public int getPartialMatchCount() { return partial_matches; } public String toString() { return "("+getRepeatCount() +(getPartialMatchCount() > 0 ? (" "+getPartialMatchCount() +"/"+unit_sequence.size()) : "") +") x "+unit_sequence; } /********** static methods below for testing **********/ static public List stringToCharList(String s) { List result = new ArrayList (); for (char c : s.toCharArray()) result.add(c); return result; } static public void test(List list) { RepeatingListFinder listFinder = new RepeatingListFinder (); for (T element : list) listFinder.process(element); System.out.println(listFinder); } static public void test(String testCase) { test(stringToCharList(testCase)); } static public void main(String[] args) { test("ABCABCABCABC"); test("ABCDFTBAT"); test("ABABA"); test("ABACABADABACABAEABACABADABACABAEABACABADABAC"); test("ABCABCABCDEFABCABCABCDEFABCABCABCDEF"); test("ABABCABABCABABDABABDABABC"); } }
这是一种面向流的方法（具有O（N）执行时间和O（N）最坏情况空间要求）; 如果要处理的List已经存在于内存中，则应该可以重写此类以处理List而不需要任何额外的空间要求，只需使用List跟踪重复计数和部分匹配计数。 subList（）创建一个单元序列，它是输入列表的前K个元素的视图。
我的解决方案，根据需要工作，也许是天真的。 它确实具有简单的优点。
String[] wta; // word text array ... INTERVAL: for(int xa=1,max=(wta.length/2); xa<=max; xa++) { if((wta.length%xa)!=0) { continue; } // ignore intervals which don't divide evenly into the words for(int xb=0; xb