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;
    }
    




  • ist mein algo wenigstens gut lesbar?





  • string find_longest_palindrome(string str) {
    

    warum nicht

    string find_longest_palindrome(const string& str) {
    

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



  • 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:

    1. das längste palindrom suchen das bei l, middle_indel, r anängt
    2. 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;
    }
    

Log in to reply