How can i find a pattern in an array of integers?

Question

A week ago I got my homework, where I have to write a function in C. The function gets a single array of positive integers, and it has to return the next number in the array. The arrays look something like this: {1,2,3,1,2,3,4,1,2,3,1,2,3,4,1,2,3,-1}; -1 means the end of the array.

I know that the number which has to be returned by the function is 1, however, how can I code a pattern finding algorithm? I haven't found any solution on the internet, since every other question about pattern searching is with strings, where the pattern which has to be found is already given.

Answer 1

if the pattern has a length of 1, you will have a[k+1] == a[k] for all possible k.

more generally, you will have a[k+plen] == a[k] for the correct plen (pattern length) and all possible k.

so determine plen starting with 1... in your case you get 7 because a[7]==a[0], a[8]==a[1], ... a[16]==a[9], so just return a[17-7].

Answer 2

Building on the answer by pmg one simple way to determine plen is to use brute force:

Begin by assuming plen is equal to 1, and increase plen by 1 until a pattern is found.

You find a pattern by checking if the sequence starting at every plen element match the first plen elements of the array. So if the current plen is 3, then you check if elements at index 3 to 5 (inclusive) matches the elements at index 0 to 2 (inclusive). If they match you check the next sequence starting at index 6. And so on.

If the end-of-array marker -1 is in the sequence you're just searching, then you have plen. And if a sequence is not matching then start over with an increased plen and try again.