Najdluzszy palindrom w ciagu

Witam,
potrzebuje algorytm ktory w czasie O(n) znajdzie najdluzszy palindrom w ciagu. wiem ze taki istnieje ale nie moge go zdobyc. mial z nim ktos kiedys kontakt ?

pozdrawiam

chodzi ci o jakis cykl ? jak tak to lecisz dwoma wskaznikami znak po znaku z tym ze jeden przesowa sie caly czas do przodu natomiast drugi ustawiasz na 0 (lub 1) jezeli natrafisz niezgodnosc :P

No ale wlasnie takie zwykle naiwne wyszukiwanie dziala zbyt dlugo a ja potrzebuje koniecznie o(n). To ponoc jest przykladowy program do przeszukiwanie tekstu w kazdej ksiazce algorytmy i ... ale ja nie znalazlem w zadnej :(

no to moze o kmp ci chodzi, a to co wyzej podalem to dziala w O(n)

nie wiem zobacze kmp ... a jak bedzie dziala ten algorytm twoj na ciagu aabccdccb bo moze go nie zrozumialem :/ najdluzszym palindromem jest bccdccb

no to co napisalem wyzej pozwala wykryc cykle w tekscie, co do palindromow to mozesz robic cos podobnego tyle ze lecisz z jednej i z drugiej strony, jezel sie spotkaja wskazniki to masz palindrom i wtedy szukasz od nowa tyle ze startujesz od tej pozycji na ktorej jestes i tak ort! a ten cykl ktory bedzie ort! to twoj ort! palindrom

"Fajnie se chopaki godocie..." ;-P

Palindromes

A palindrome is a string, P, such that P=reverse(P). e.g. abba'=reverse(abba'). e.g. ississi' is the longest palindrome in mississippi'.

The longest palindrome of txt[1..n] can be found in O(n) time, e.g. by building the suffix tree for txt$reverse(txt)# or by building the generalized suffix tree for txt and reverse(txt).

palindrome substring

Tak wiem doszedlem juz do tego. Problem mozna rozwiazac na drzewie (suffix tree) niestety nie wiem jak. Ponizej napisalem moj kod do rozwiania tego problemu w czasie O(n^2). Moze sie przyda do sprawdzenia poprawnosci algorytmu.

void najdluzszyPalindrom(int n, char *ciag, int *maxLength, int *maxAdres)
{
    int i,j,k,length,adres;
    
    for(i=1,length=0; i<n; i++)
    { 
        for(j=0,k=i; j<k; j++)
        {
            if(ciag[k]==ciag[j])
            {
                if((k-j+1)>length)
                {
                    adres=j;
                    length=k-j+1;
                }
                k--;    
            }
            else
            {
                if(length)
                {
                    j--;
                    k=i;
                    length=0;
                }
            } 
        }                
        
        if(length>*maxLength)
        {
            *maxLength=length;
            *maxAdres=adres;
        }    
    }    
}

Nie pamiętam jak się ten algorytm nazywał ale widziałem go w książce
"Algorytmy i struktury danych" bodajże K.Diksa. Jeśli masz do niej dostęp to sprawdź.

jak zaimplementujesz ND maszyne turinga to bedziesz mial juz z gorki powodzenia poszukaj na googlach