algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Manachera - Implementacja w C/C++
Ocena użytkownikóww: *****  / 8
SłabyŚwietny
Nadesłany przez Emil Hotkowski, 01 lutego 2012 22:13
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

manacher.cpp:
//Algorytm Manachera
//www.algorytm.org
//Emil Hotkowski

#include <cstdlib>
#include <iostream>
#define N 10 //Dlugosc rozpatrywanego slowa

using namespace std;

//Funkcja pomocnicza - zwraca maksimum z dwoch liczb
inline int max(int a ,int b)
{
    if(a >b)return a;
    else return b;
}

//Funkcja pomocnicza - zwraca minimum z dwoch liczb
inline int min(int a ,int b)
{
    if(a <b)return a;
    else return b;
}       

//Program
int main(int argc, char *argv[])
{
    char s[N+2]; //utworz tablice przechowywujaca slowo
    int R[N+2];  //utworz tablice przechowywujaca rozwiazania
    s[0]='#';    //specjalny znacznik poczatku slowa (nie moze wystepowac w slowie)
    s[N]='$';    //specjalny znacznik konca slowa (nie moze wystepowac w slowie)
    for(int i = 1; i <= N; i++) cin >> s[i];//pobierz N znakow
    
    //Oblicz promienie palindromow parzystych
    int i = 1;
    int t = 0;
    R[0] = 0;
    while(i <= N)
    {
        while(s[i-t] == s[i + t+1])t++; //oblicz wielkosc palindromu parzystego o srodku w punkcie i
        R[i] = t;

        //Algorytm Manachera
        int k = 1;
        while(k <= t && R[i - k] != R[i] - k)
        {
            R[i + k] = min(R[i-k],(R[i]-k));
            k++;
        }
        t-=k;
        t=max(0,t);
        i+=k;
    }       
    
    //Wypisz wyniki
    for(int i = 1; i <= N; i++) cout << s[i] << " ";
    cout << "\n" << " ";
    for(int i = 1; i < N; i++) cout << R[i] << " ";     
    
    system("PAUSE");
    return EXIT_SUCCESS;
}
Komentarze
photo
0 # hauleth 2013-07-26 22:15
Bez sensu są własne implementacje `min` i `max` skoro używa się tu C++ (obie są zawarte w ``). Poza tym jako znaczniki początku i końca zalecał bym '\0x02' oraz '\0x03', czyli Start Of Text i End Of Text (http://pl.wikipedia.org/wiki/ASCII).
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz