Обнаружение, когда серия символов повторяется лучше, чем O (n!)

Question

Мне нужно найти, когда серия символов (на самом деле это действительно длинное число) начинает повторяться. Я подумал, что шаблон будет проще всего. Может кто-нибудь мне помочь?

Answer 1

Если это число, начните с конца.

Найдите последовательность, для которой последняя n и вторая последняя n цифра совпадают, что повторяется по наибольшему количеству цифр.O (n)

Там, где повторяющаяся последовательность останавливается (идет с конца), где начинается повторение.

Например, скажем, у вас 1,2340111101111

Вы видите 1 повторяется, но только для 4 цифр.01111 повторяется для 10 цифр, означая, что повторение начинается после 1.234

Answer 2

Я не знаю Java.Я не уверен в вашем точном вопросе, но кажется, что вы пытаетесь найти максимальную орбиту последовательности.Следующий псевдокод должен помочь:

Given sequence M of length N
Initialize list of indices K
foreach index i from N-1 to N/2
    seqLength := N-i
    isOrbit? := true
    foreach index s from 0 to seqLength-1
        if M[N-1-s] != M[N-1-seqLength-s] then
            isOrbit? := false
    if isOrbit? then
       append(K, i)

Самая длинная орбита, конечно, последняя запись, добавленная в K. Алгоритм O (n ^ 2/4) или около того.По сути, это модифицированный алгоритм поиска подпоследовательности.

Answer 3

В зависимости от того, откуда происходит эта последовательность, это может быть полезно .