Searching algorithm

Question

I'm looking for a efficient searching algorithm to get the longest shortest repeated pattern in a collection (~2k of integers), where my collection is made of this repeated pattern only (there is no noise between repeated patterns), but the last occurence of pattern may be incomplete.

Examples: I've got: [2,4,1, 2,4,1, 2,4,1, 2,4,1, 2,4,1]
I'd like to recieve: [2,4,1]

I've got: [21,1,15,22, 21,1,15,22, 21,1,15,22, 21,1,15]
I'd like to recieve: [21,1,15,22]

I've got: [3,2,3,2,5]
I'd like to recieve: [] (there is no pattern)

(spaces added just for readability)

Answer 1

The very straight forward algorithm would look like this (in Python, but should be no problem to translate to Javascript):

def check(a, width):
  '''check if there is a repeated pattern of length |width|'''
  for j in range(width, len(a)):
    if a[j] != a[j-width]:
      return False
  return True

def repeated(a):
  '''find the shortest repeated pattern'''
  for width in range(1, len(a)):
    if check(a, width):
      return a[:width]
  return []

This should also be rather efficient, since most of the time the loop in check() will return right in the first iteration, so that you basically only iterate over the list once.

Answer 2

Try building up your initial grouping by starting at the beginning adding a number to the group until you get to a number that is the same as the first in the group (the previous number terminates the pattern). Use this as your test pattern and go through, matching the pattern until you get a failure. If you match the entire collection (with your special end pattern handling) that is one candidate. Go back to the place where you found your initial match, then continue building up your group until you get to another number matching the first in your pattern. Repeat, replacing your candidate whenever you find a longer one. When your pattern is the same length as the collection stop (this one doesn't match). If you have a candidate that will be the longest pattern.