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; }
-
ja kann man noch schneller machen
http://en.wikipedia.org/wiki/Longest_palindromic_substring
-
ist mein algo wenigstens gut lesbar?
-
nö
-
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
* dassget_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; }