Возможно периодические последовательности и их детекция

[denny]

Сейчас занимаюсь автоматами на строках/массивах, по типу SubstitutionSystem и SequenceReplace Mathematica.
На выходе часто встречаются кандидаты на almost periodic, аналоги Tue-Morse.
Иногда попадаются eventually ("в конечном итоге") periodic. И вот их хотелось бы как-то отбирать, детектировать.
Но разумеется, все мои последовательности конечны. Доказательство того, что вся Tue-Morse almost periodic нетривиально,
я занимаюсь только численными экспериментами.

Читал разные материалы на эту тему. В результате пришел к такому наивному определению.
Возможно периодической в конечном итоге последовательностью назовем конечную группу паттернов:

$$\mathbb{HPP…T}$$

где:
$\mathbb{H}$ - (Head) префикс любого вида, возможно пустой, возможно периодический и т.д.
$\mathbb{P}$ - паттерн, который повторяется после $\mathbb{H}$ минимум два раза
$\mathbb{T}$ - (Tail) суффикс, любой префикс $\mathbb{P}$, то есть предполагаемое начало следующего периода

Буду признателен за любые комментарии на это определение!
Но в любом случае, похоже оно не глупое. Поэтому я начал пытаться его детектировать.
Единственный разумный вариант (опять же после чтения сабжа) - использование Z-функции или префикс-функции.
Уверен, что именно они помогут в детектировании искомого паттерна,
но как-то не складывается в голове, как это оформить четко и эффективно.

[maxal]

С этой задачей должен справляться Walnut: https://cs.uwaterloo.ca/~shallit/walnut.html

[mihaild]

Несложно заметить, что если потребовать, чтобы паттерн повторялся ровно 2 раза, то определение не поменяется (лишние вхождения можно включить в префикс).

Разверните строку и посчитайте значение префикс-функции в точке $|T| + 2\cdot |P|$ (для случая периодических строк). Подумайте, как просто по этому значению (и еще одному числу) понять, что данная точка может рассматриваться как начало периода.