algorithm - 模式查找器算法

Question

我想编写一个能够检测任何模式并确定下一个元素的算法。一些示例是 11 22 11 22 1，其中下一个元素是 1。

但它也可以是 3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1 (1x3 , 4x1, 3x3, 3x1, 3x3, 4x1) 其中下一个元素将是 3。

所以它总是这样:3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1 3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1

我们不知道模式有多长，但我们知道它在数组中至少出现过一次。我们也知道只有一种模式，而且 100% 都在数组内部。

将数字想象成颜色可能会很有用，而数组将是一堵墙，上面有重复的墙纸。因此，我们的任务是确定如果它继续下去，墙会是什么颜色。

我应该如何开始？

Answer 1

您可以搜索可以在字符串中的其他任何位置找到的最长后缀。而不是简单地在其他位置添加后缀后面的字符。

例子3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1

我们可以在序列的其他地方(而不是末尾)找到以下后缀

1            (found at a lot of positions)   
1 1          (found at a lot of positions)  
1 1 1        (found at a lot of positions)  
1 1 1 1      (found at position 1)  
3 1 1 1 1    (found at position 0)  
3 3 1 1 1 1  (does not appear anywhere in the sequence except at  the end)  

所以最长的后缀是 3 1 1 1 1，后面是 3。

3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1  
xxxxxxxxx ^

所以下一个字符的估计规则是 3 。