Как вычислить палиндром из потока символов в сублинейном пространстве / времени?

Question

Я даже не знаю, существует решение или нет.Здесь проблема в деталях.Вы - программа, которая принимает бесконечно длинный поток символов (для простоты вы можете предположить, что символы равны 1 или 0).В любой момент я могу остановить поток (скажем, через N символов) и спросить вас, является ли полученная строка палиндромом или нет.Как вы можете сделать это, используя меньше сублинейного пространства и / или времени.

Answer 1

Да. Ответ примерно на две трети пути вниз http://rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/

РЕДАКТИРОВАТЬ: Некоторые люди просили меня подвести итоги в случае, если ссылка умрет. Ссылка дает некоторые подробности о доказательстве следующей теоремы: Существует многоленточная машина Тьюринга, которая может распознавать начальные нетривиальные палиндромы в режиме реального времени. (Резюме, также приведенное в статье, на которую дана ссылка : Предположим, что машина прочитала входные данные x1, x2, ..., xk , тогда у нее есть только постоянное время, чтобы решить, является ли x1, x2, ..., xk палиндром.)

Многоканальная машина Тьюринга - это всего лишь одна машина с несколькими параллельными лентами, на которые она может читать и записывать; в определенном смысле это в точности эквивалентно стандартной машине Тьюринга.

Вычисление в реальном времени - это вычисление, в котором машина Тьюринга должна считывать символ с ввода по крайней мере один раз каждые M шагов (для некоторой ограниченной константы M). Легко видеть, что любой алгоритм реального времени должен быть линейным, тогда.

Существует документ с доказательством, который составляет около 10 страниц, который доступен за институциональной платой здесь , который я не буду размещать в других местах. Вы можете связаться с автором для более подробного объяснения, если хотите; Я только что прочитал это недавно и понял, что это более или менее то, что вы искали.

Answer 2

Вы можете использовать скользящий хеш или более скользящих хешей для точности.Поэтапно вычисляйте хэш прочитанных до сих пор символов, в порядке их чтения и в обратном порядке чтения.

Если ваша хеш-функция равна, например, x*3^(k-1)+x*3^(k-2)+...+x*3^0, где x - это символ, который вычитай, вот как ты это сделаешь:

hLeftRight = 0
hRightLeft = 0
k = 0

repeat until there are numbers in the stream
    x = stream.Get()    

    hLeftRight = 3*hLeftRight + x.Value
    hRightLeft = hRightLeft + 3^k*x.Value

    if (x.QueryPalindrome = true)
        yield hLeftRight == hRightLeft

    k = k + 1

Очевидно, что тебе придется вычислять хэши по модулю чего-то, вероятно, простого числа или степени двойки.И, конечно, это может привести к ложным срабатываниям.

Answer 3

Это может помочь вам: http://arxiv.org/pdf/1308.3466v1.pdf

Если вы храните последние $ k $ много входных символов, вы легко можете найти палиндромы до длины $ k $.
Если вы используете алгоритмы из статьи, вы можете найти середины палиндромов и оценку длины его длины.

Answer 4

Раунд 2

На мой взгляд, с каждым новым персонажем есть три случая:

1. Символ нарушает потенциальную симметрию, например, aab -> aabc
2. Символ расширяет середину, например aab -> aabb
3. Символ продолжает симметрию, например aab-> aaba

Предположим, у вас есть указатель, который отслеживает строку и указывает на последний символ, который продолжил потенциальный палиндром.

(я собираюсь использовать круглые скобки для обозначения заостренного символа)

Допустим, вы начинаете с aa (b) и получаете:

• 'a' (случай 3), вы перемещаете указатель на слева и проверьте, является ли это «а» (это является). Теперь у вас есть (а) б.
• «c» (случай 1), вы не ожидаете «c», в этом случае вы начинаете с начала и теперь у вас есть aab (c).

Действительно сложный случай - 2, потому что каким-то образом вы должны знать, что только что полученный персонаж не влияет на симметрию, он просто расширяет середину. Для этого вы должны держать дополнительный указатель, который отслеживает, где лежит край плато (середины). Например, у вас есть (b) baabb, и вы только что получили другое «b», в этом случае вы должны знать, чтобы сбросить указатель на основание среднего плато здесь: bbaa (b) bb. Так как мы идем на постоянное время, вы должны держать указатель здесь для начала (вы не можете позволить себе время для поиска края плато). Теперь, если вы получили еще один «b», вы знаете, что вы все еще на краю этого плато, и вы удерживаете указатель там, где он находится, поэтому bbaa (b) bb -> bbaa (b) bbb. Теперь, если вы получаете «a», вы знаете, что «b» не являются частью расширенной середины, и вы сбрасываете оба указателя (указатель отслеживания и указатель края), так что теперь у вас есть bbaabbbb ((a)).

В этих трех случаях я думаю, что все базы покрыты. Если вы когда-нибудь захотите проверить, является ли текущая строка палиндромом, проверьте, имеет ли первый указатель (не указатель края плато) индекс 0.