spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

C-/C++-Quelltext

//////////////////////////////////////////////////////////////////////////

// spieleprogrammierer.de-Programmier-Contest #02                       //

// ******************************************************************** //

// Titel: ...... "Palindrom"                                            //

// Typ: ........ Kürze des Codes                                        //

// Deadline: ... 20.01.2008                                             //

// Abgabe: ..... contest@spieleprogrammierer.de                         //

// ******************************************************************** //

// Aufgabe:                                                             //

// --------                                                             //

// Deine Funktion erhält als Eingabe einen String und muss die Länge    //

// des längsten Palindroms innerhalb dieses Strings zurückgeben.        //

// Ein Palindrom ist ein String, der vorwärts wie rückwärts gelesen     //

// dasselbe ergibt. Beachte: ein Substring mit nur einem einzigen       //

// Zeichen ist immer ein Palindrom. Bei einem leeren String als Eingabe //

// ist die korrekte Ausgabe die Null.                                   //

// Jegliche Benutzung der Standardbibliothek ist verboten!              //

//////////////////////////////////////////////////////////////////////////


#include <iostream>

//////////////////////////////////////////////////////////////////////////


// >>> EIGENE FUNKTION - BITTE IMPLEMENTIEREN! <<<

// >>> BENUTZUNG DER STANDARDBIBLIOTHEK IST VERBOTEN! <<<

size_t my_palindrome(const char* p_string)
{
    return 0;
}

//////////////////////////////////////////////////////////////////////////


// Referenzfunktion, zum Vergleich

size_t reference_palindrome(const char* p_string)
{
    // Länge des Strings bestimmen

    size_t string_length = 0;
    while(p_string[string_length]) ++string_length;

    // Leerer String?

    if(string_length == 0) return 0;

    size_t longest_palindrome = 1;
    for(size_t start = 0; start < string_length; ++start)
    {
        for(size_t end = start + 1; end < string_length; ++end)
        {
            const size_t substring_length = end - start + 1;
            bool found = true;

            if(substring_length % 2)
            {
                // ungerade Länge

                const size_t center = (start + end) / 2;
                for(size_t i = 0; i <= substring_length / 2; ++i)
                {
                    if(p_string[center - i] != p_string[center + i])
                    {
                        found = false;
                        break;
                    }
                }
            }
            else
            {
                // gerade Länge

                for(size_t i = 0; i < substring_length / 2; ++i)
                {
                    if(p_string[start + i] != p_string[end - i])
                    {
                        found = false;
                        break;
                    }
                }
            }

            // Längeres Palindrom gefunden?

            if(found && substring_length > longest_palindrome)
                longest_palindrome = substring_length;
        }
    }

    return longest_palindrome;
}

//////////////////////////////////////////////////////////////////////////


int main()
{
    const char* p_test[] = { "",
                             "x",
                             "aa",
                             "ab",
                             "nix",
                             "xyx",
                             "otto",
                             "abcd",
                             "abcabacab",
                             "ottoottoottoerikafeuertnuruntreuefakire123" };

    bool all_correct = true;
    for(size_t i = 0; i < sizeof(p_test) / sizeof(p_test[0]); ++i)
    {
        const size_t reference_result = reference_palindrome(p_test[i]);
        const size_t my_result = my_palindrome(p_test[i]);
        const bool correct = reference_result == my_result;
        all_correct &= correct;
       
        std::cout << "s = \"" << p_test[i] << "\": " << std::endl;
        std::cout << "reference_palindrome(s) = " << reference_result << std::endl;
        std::cout << "my_palindrome(s)        = " << my_result << std::endl;
        std::cout << (correct ? "Richtig!" : "Falsch!") << std::endl;
        std::cout << std::endl;
    }

    std::cout << (all_correct ? "Alles richtig!" : "Es gab einen oder mehrere Fehler!") << std::endl;
    std::cout << std::endl << std::endl;

    return 0;
}