Search algorithm

Question

I am looking for an effective search algorithm to get long the shortest repeating pattern in the collection (~ 2k integers), where my collection is made from this only repeating pattern (there is no noise between repeating patterns), but the last appearance of the pattern may be incomplete.

Examples: I have: [2,4,1, 2,4,1, 2,4,1, 2,4,1, 2,4,1]
I would like to get:[2,4,1]

I have: [21,1,15,22, 21,1,15,22, 21,1,15,22, 21,1,15]
I would like to receive:[21,1,15,22]

I have: [3,2,3,2,5]
I would like to receive: [](no template)

(spaces added for readability only)

Answer 1

( Python, 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 []

, check() , .

Answer 2

, , , , ( ). , , . ( ), . , , , , . , , . , - ( ). , .

Answer 3

, , . A [] T, A [i + T] = A [i] i. , T, , A [0..T-1] - , . , T = 1 , . , ( , ). T , A [i + T] = A [i] = 0..A.len-T-1. .

Answer 4

You can optimize your search by noting that the length of your collection should be a multiple of your template length. If your collection has a size that is simple, the only possible template length is 1, i.e. All items must be the same!