Wie überprüft man, ob eine Zeichenfolge mit einem Palindrom beginnt?

Question

Ich möchte überprüfen, ob eine Zeichenfolge mit einem palindromischen Teilstring beginnt; Ich suche nach dem längsten palindromischen Teilstring, der mit dem Start meines Arrays beginnt. Dies ist ein trivialer Ansatz in O(n*n). Gibt es einen klügeren Weg?

//not safe for empty string 
bool isPalindrome(string s) 
{ 
    string rev = s; 
    std::reverse(rev.begin(), rev.end()); 
    return rev == s; 
} 

int startWithPalindome(const string a) 
{ 
    int N = a.length(); 
    for (int len = N; len > 0; len--) 
    { 
     bool isPal = isPalindrome(a.substr(0,len)); 
     if (isPal) 
      return len; 
    } 

    return -1; 
} 

EDIT: Klarstellung: Ich weiß, dass dieser Code kann auf viele Art und Weise verbessert werden, variout zwickt zu tun, aber ich bin interessiert an asymptotische Zeitkomplexität zu reduzieren.

Answer 1

optimiert startWithPalindrome()

Ihr Ansatz ist für die größtmögliche Palindrom zu suchen, und Brute-Force verwendet nacheinander die Größe des Teils zu reduzieren, die Sie berücksichtigen, bis Sie ein Palindrom finden.

Sie könnten leicht viele Vergleiche löschen, indem Sie nicht mit der Gesamtgröße der Zeichenkette beginnen, sondern nach dem letzten Vorkommen der ersten Zeichenkette unter Verwendung von rfind() suchen. Dann könnten Sie durchlaufen auf die vorherige Position dieses Zeichen und so weiter:

int startWithPalindome(const string a) 
{ 
    if (a.length()>1) 
    { 
     for (int N = a.rfind(a[0]); N!=string::npos && N>0; N= a.rfind(a[0],N-1)) { 
      if (isPalindrome(a.substr(0,N+1))) 
       return N+1; 
     } 
    } 
    return -1; 
} 

Durch die Art und Weise: Optimierung der isPalindrome()

Ihre Version von isPalindrom() einen leeren String oder ein einzelnes Zeichen betrachtet Schnur als Palindrom. Sie könnten es so behalten, aber ich würde vorschlagen, solche Fälle zu beseitigen.

Ich schlage vor, Sie dennoch eine kleine Variante, die nicht die Zeichenkette kopiert, sondern nur durchläuft es von Anfang bis Ende, also tun (fast) die kleinste Anzahl von Operationen:

bool isPalindrome(string s) 
{ 
    if (s.length()<2)  // empty strings and singles chars are no palindromes ! 
     return false; 
    for (auto f=s.cbegin(), r=s.cend()-1; f!=r; r--) { 
     if (*f!=*r)   // if the nth letter from start doesn't match nth from ens 
      return false;  // not a palindrom 
     if (++f==r)   // if middle of string is between two chars 
      break;  
    } 
    return true;   // we meet in the middle so it's a palindrome 
} 

Online demo