c - 如何在整数数组中找到模式？

Question

一周前我做了作业，我必须用 C 语言编写一个函数。该函数获取一个正整数数组，它必须返回数组中的下一个数字。数组看起来像这样：{1,2,3,1,2,3,4,1,2,3,1,2,3,4,1,2,3,-1}; -1 表示数组的结尾。

我知道函数必须返回的数字是 1，但是，如何编写模式查找算法？我在互联网上没有找到任何解决方案，因为关于模式搜索的所有其他问题都与字符串有关，必须找到的模式已经给出。

Answer 1

如果模式的长度为1，那么您将拥有a[k+1] == a[k]所有可能的k。

更一般地说，您将拥有a[k+plen] == a[k]正确的plen（模式长度）和所有可能的k.

所以确定plen从1... 开始，在你的情况下，你会得到7because a[7]==a[0], a[8]==a[1], ... a[16]==a[9]，所以只需 return a[17-7]。

Answer 2

基于pmg的答案，一种简单的确定方法plen是使用蛮力：

首先假设plen等于，1然后增加直到找到模式。plen1

您可以通过检查从每个元素开始的序列是否与数组plen的第一个元素匹配来找到模式。plen因此，如果当前plen是3，那么您检查索引到（包括）处的元素是否与索引到3（5包括）处的元素匹配。如果它们匹配，则检查从 index 开始的下一个序列。等等。026

如果数组结尾标记-1在您刚刚搜索的序列中，那么您有plen. 如果序列不匹配，则从增加的序列重新开始，然后plen重试。