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.

You shouldn't have gotten homework about something which wasn't taught in the class, so please go through your class-notes and see if you can find a hint there. — Some programmer dude, Nov 01 '19 at 12:11
The possible inputs are an array of integers, and in general they look something like this: 1,2,3,1,2,3,1,2,-1; where -1 means the end of the array, as the description of my homework states. — Balázs Szombati, Nov 01 '19 at 12:13

score 3 · Answer 1 · answered Nov 01 '19 at 12:20

3

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].

answered Nov 01 '19 at 12:20

pmg

106,608
13
126
198

1

alternatively just say the pattern is the whole input and return the 1st element :) – pmg Nov 01 '19 at 12:22

Some programmer dude · Answer 2 · 2019-11-01T12:46:14.790

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.

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

2 Answers2

Linked