laengstes palindrom algo

hi,
bitte um feedback zum folgenden algo. im moment ist die laufzeit des algos O(n^2), speicher: O(1)
was kann die laufzeit noch schneller machen?

#include <iostream>
#include <string>
using namespace std;

void get_longest_pal(const string &s, int middle_index, int l, int r, string &longest_pal) {
	bool found = false;
	string pal;

	if(middle_index != -1) {
		pal = s[middle_index];
	}

	while(l >= 0 && r < s.size()) {
		if(s[l] == s[r]) {
			pal = pal + s[r];
			pal = s[l] + pal;
			found = true;
			l--;
			r++;
		}
		else {
			break;
		}
	}

	if(found && pal.size() > longest_pal.size()) {
		longest_pal = pal;
	}
}

string find_longest_palindrome(string str) {
	string longest_pal;

	for(int i = 0; i < str.size(); i++) {
		// pair element in the middle
		if(i < str.size() - 1 && str[i] == str[i+1]) {
			get_longest_pal(str, -1, i, i+1, longest_pal);
		}	
		// single element in the middle
		if(i < str.size() - 2 && str[i] == str[i+2]) {
			get_longest_pal(str, i+1, i, i+2, longest_pal);
		}
	}

	return longest_pal;
}

int main() {
	// your code goes here

	cout << find_longest_palindrome("aaabbaaaccdeqjncsdddmmmkkkmmmddd") << endl;

	return 0;
}

hustbaer

ja kann man noch schneller machen
http://en.wikipedia.org/wiki/Longest_palindromic_substring

ist mein algo wenigstens gut lesbar?

hustbaer

nö

string find_longest_palindrome(string str) {

warum nicht

string find_longest_palindrome(const string& str) {

wird ja weder verändert noch sonst was...

hustbaer

Wobei... hauptsächlich stört:
* dass du recht unsprechende Variablennamen verwendest
* dass get_longest_pal zwei dinge macht die ich persönlich auftrennen würde:

das längste palindrom suchen das bei l, middle_indel, r anängt
gucken ob es länger als das bisher gefundene längste palindrom ist und ggf. longest_pal updaten

Dass du pal während der Suche zusammenbaust verwirrt auch eher.

Nach ein paar kleinen Umbauten sieht dein Code so aus, was ich persönlich besser zu lesen finde:

string get_longest_palindrome_at(string const& s, int left_index, int right_index)
{
    assert(left_index + 1 == right_index || left_index + 2 == right_index);

    // check if there is a palindrome with that center position (mid-point between left_index and right_index) at all
    if (s[left_index] != s[right_index])
        return "";

    // extend bounds as much as possible
    while (left_index > 0 && (right_index + 1) < s.size())
    {
        if (s[left_index - 1] == s[right_index + 1])
        {
            left_index--;
            right_index++;
        }
        else
            break;
    }

    return string(s.begin() + left_index, s.begin() + right_index + 1);
}

void update_longest_palindrome(string const& s, int left_index, int right_index, string& longest_palindrome)
{
    // update longest_palindrome by comparing with the longest palindrome with the specified
    // center position (mid-point between left_index and right_index)
    if (left_index >= 0 && right_index < s.size())
    {
        string const candidate = get_longest_palindrome_at(s, left_index, right_index);
        if (candidate.size() > longest_palindrome.size())
            longest_palindrome = candidate;
    }
}

string find_longest_palindrome(string const& s)
{
    string longest_palindrome;

    for (int i = 0; i < s.size(); i++)
    {
        // pair element in the middle
        update_longest_palindrome(s, i, i + 1, longest_palindrome);

        // single element in the middle
        update_longest_palindrome(s, i, i + 2, longest_palindrome);
    }

    return longest_palindrome;
}