Jak obliczyć palindrom ze strumienia znaków w podliniowej przestrzeni/czasie?

Question

Nie wiem nawet, czy istnieje rozwiązanie, czy nie. Oto problem w szczegółach. Jesteś programem, który przyjmuje nieskończenie długi strumień znaków (dla uproszczenia możesz założyć, że postacie mają 1 lub 0). W dowolnym momencie mogę zatrzymać strumień (powiedzmy po przejściu N znaków) i zapytać, czy otrzymany do tej pory ciąg znaków jest palindromem, czy nie. Jak możesz to zrobić, używając mniej podliniowej przestrzeni i/lub czasu.

Answer 1

Do dokładności można użyć wartości rolling hash lub więcej mieszających się skrótów. Przyrostowo obliczyć skrót znaków odczytanych do tej pory, w kolejności, w której zostały odczytane, w odwrotnej kolejności od czytania.

Jeśli funkcja skrótu jest x*3^(k-1)+x*3^(k-2)+...+x*3^0 na przykład, gdzie x to postać czytasz, to jak chcesz to zrobić:

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 

Oczywiście trzeba by obliczyć hashe modulo coś, prawdopodobnie prime lub moc dwóch. I oczywiście może to prowadzić do fałszywych alarmów.

Answer 2

Tak. Odpowiedź jest około dwie trzecie drogi w dół http://rjlipton.wordpress.com/2011/01/12/stringology-the-real-string-theory/

EDIT: Niektórzy ludzie pytali mnie do podsumowania wyników, w przypadku matryc link. Łącze podaje kilka szczegółów na temat dowodu następującego twierdzenia: Istnieje wielościeżkowa maszyna Turinga, która rozpoznaje początkowe nietrywialne palindromy w czasie rzeczywistym. (Podsumowanie, również dostarczone przez artykuł związany: Załóżmy, że komputer odczytał x1, x2, ..., xk wejścia, a następnie ma tylko stały czas, aby zdecydować, czy x1, x2, ..., xk jest palindromem.)

Multitapowa maszyna Turinga to tylko jedna z taśmami side-by-side, do których można odczytywać i zapisywać; w bardzo konkretnym znaczeniu jest to dokładnie odpowiednik standardowej maszyny Turinga.

Obliczenia w czasie rzeczywistym to takie, w których maszyna Turinga musi odczytać znak z wejścia co najmniej raz na każde M kroki (dla pewnej stałej ograniczonej M). Łatwo zauważyć, że każdy algorytm czasu rzeczywistego powinien być wtedy liniowy.

Na teście znajduje się dokument, który ma około 10 stron, dostępny za płatną zaporą instytucjonalną here, którego nie będę publikować w innym miejscu. Jeśli chcesz, możesz skontaktować się z autorem, aby uzyskać bardziej szczegółowe wyjaśnienie; Właśnie czytałem to ostatnio i zdałem sobie sprawę, że to mniej więcej to, czego szukałeś.

Answer 3

Runda 2

Jak ja to widzę, z każdą nową postać, istnieją trzy przypadki:

1. postaci przerw potencjalnego symetrii, na przykład, AaB -> aabc
2. Charakter rozciąga się w środku , na przykład AaB -> AABB
3. Charakter nadal symetrii, na przykład aab-> Aaba

Załóżmy, że masz wskaźnik, który śledzi ciąg znaków i wskazuje na ostatni znak, który kontynuował potencjalny palindrom.

(mam zamiar użyć nawiasów oznaczać wskazał na postać)

Powiedzmy, że zaczynają z AA (b) i uzyskać:

• 'a' (przypadek 3), przesuwasz wskaźnik na po lewej stronie i sprawdzasz, czy jest to "a" (to ). Masz teraz (a) b.
• "c" (przypadek 1), nie spodziewasz się litery "c", w tym przypadku zaczynasz od początku, a teraz masz aab (c).

Bardzo podchwytliwa sprawa to 2, ponieważ jakoś musisz wiedzieć, że postać, którą właśnie dostałeś, nie wpływa na symetrię, tylko rozszerza środek. W tym celu należy trzymać dodatkowy wskaźnik, który śledzi położenie krawędzi plateau (środkowej). Na przykład masz (b) baabb, a dostałeś kolejny "b", w tym przypadku musisz wiedzieć, aby zresetować wskaźnik do podstawy środkowego plateau tutaj: bbaa (b) bb. Ponieważ idziemy na stały czas, na początku musisz mieć wskaźnik (nie możesz sobie pozwolić na czas na szukanie krawędzi płaskowyżu). Teraz, jeśli dostaniesz inny "b", wiesz, że wciąż jesteś na skraju tego płaskowyżu i trzymasz wskaźnik tam, gdzie jest, więc bbaa (b) bb -> bbaa (b) bbb. Teraz, jeśli otrzymasz "a", wiesz, że 'b' nie są częścią rozszerzonego środka i resetujesz oba wskaźniki (wskaźnik śledzenia i wskaźnik krawędzi), więc masz teraz bbaabbbb ((a)).

W tych trzech przypadkach myślę, że wszystkie bazy są objęte gwarancją. Jeśli kiedykolwiek chciał sprawdzić, czy obecny ciąg jest palindrom, sprawdź czy pierwszy wskaźnik (nie płaskowyżu za wskaźnik krawędzi) jest w indeksie 0.

Answer 4

To może pomóc: http://arxiv.org/pdf/1308.3466v1.pdf

jeśli przechowywać ostatnie $ k $ wiele symboli wejściowych możesz łatwo znaleźć palindromy do długości $ k $.
Jeśli używasz algorytmów papieru, możesz znaleźć punkty środkowe palindromów i oszacować długość ich długości.