Поиск повторяющейся последовательности в конце последовательности чисел

Моя проблема в следующем :У меня есть большая последовательность чисел. Я знаю, что после некоторого момента она становится периодической -, то есть в начале последовательности есть k чисел, а затем есть еще m чисел, которые повторяются до конца последовательности. В качестве примера, чтобы сделать это более понятным, последовательность может выглядеть так :[1, 2, 5, 3, 4, 2, 1, 1, 3, 2, 1, 1, 3, 2, 1, 1, 3,...], где k равно 5, а m равно 4, и тогда повторяющийся блок будет [2, 1, 1, 3]. Как видно из этого примера, у меня могут быть повторяющиеся биты внутри большего блока, поэтому просто искать первые экземпляры повторения не помогает.

Однако я не знаю, что такое k или m -моя цель состоит в том, чтобы взять последовательность [a _1, a _2,..., a _n] в качестве входных данных и выведите последовательность [a _1,..., a _k, [a _(k+1 ),..., a _(k+m )]] -в основном усекая более длинную последовательность, перечисляя большую ее часть как повторяющийся блок.

Есть ли эффективный способ решить эту проблему? Кроме того, вероятно, сложнее, но более идеально с вычислительной точки зрения -. Возможно ли это сделать, когда я генерирую рассматриваемую последовательность, чтобы мне пришлось генерировать минимальное количество? Я просмотрел другие похожие вопросы на этом сайте, но все они, кажется, имеют дело с последовательностями без начального неповторяющегося бита -и часто без необходимости беспокоиться о внутреннем повторении.

Если это поможет/будет полезно, я также могу рассказать, почему я смотрю на это и для чего я буду это использовать.

Спасибо!

РЕДАКЦИИ :Во-первых, я должен был упомянуть, что я не знаю, заканчивается ли входная последовательность точно в конце повторяющегося блока.

Проблема реального -мира, над которой я пытаюсь работать, состоит в том, чтобы написать красивое выражение в замкнутой -форме для разложений в непрерывные дроби (CFE )квадратичных иррациональных чисел (на самом деле, отрицательное CFE ). Очень просто сгенерировать частичные частные *для этих CFE с любой степенью точности -, однако в какой-то момент хвост CFE для квадратичного иррационального числа становится повторяющимся блоком. Мне нужно работать с частичными частными в этом повторяющемся блоке.

Мои текущие мысли таковы: :возможно, я смогу адаптировать некоторые из предложенных алгоритмов, которые работают справа, для работы с одной из этих последовательностей. В качестве альтернативы, возможно, в доказательстве того, почему квадратичные иррациональные числа являются периодическими, есть что-то, что поможет мне понять, почему они начинают повторяться, что поможет мне найти несколько простых критериев для проверки.

*Если я записываю разложение цепной дроби как [a _0, a _1,...], я называю a _i частичными частными.

Некоторые справочные сведения можно найти здесь для тех, кому интересно:http://en.wikipedia.org/wiki/Periodic_continued_fraction