Dize uygulamasında en büyük palindromu bulma

Question

20.000 karaktere kadar bir dizede en büyük palindromu bulmak için soran bir sorunu çözmeye çalışıyorum. Her alt dizgeyi çalıştıran bir palindrom olup olmadığını kontrol etmeye çalıştım, ama açıkça çok yavaştı. Küçük bir müdavimin ardından bu güzel algoritmayı http://stevekrenzel.com/articles/longest-palnidrome buldum. Bunu uygulamaya çalıştım, ancak işe yaramayacağım. Ayrıca, verilen dize geçersiz karakterler içeriyor, bu yüzden onu yalnızca yasal karakterlere dönüştürmek ve tüm karakterler ile en uzun palindromu çıkarmak zorundayım.

int len = original.length(); 
int longest = 0; 
string answer; 

for (int i = 0; i < len-1; i++){ 

    int lower(0), upper(0); 

    if (len % 2 == 0){ 
     lower = i; 
     upper = i+1; 
    } else { 
     lower = i; 
     upper = i; 
    } 

    while (lower >= 0 && upper <= len){ 
     string s2 = original.substr(lower,upper-lower+1); 
     string s = convert(s2); 

     if (s[0] == s[s.length()-1]){ 
      lower -= 1; 
      upper += 1; 
     } else { 
      if (s.length() > longest){ 
       longest = s.length(); 
       answer = s2; 
      } 
      break; 
     } 


    } 
} 

ben kağıt üzerinde tam olarak bu algoritma kullanılarak denedim ve lütfen yardım çalıştı, işe alınamıyor:

İşte benim denemesi. Eğer gerekiyorsa İşte tam kod: http://pastebin.com/sSskr3GY

DÜZENLEME: Tamam

int longest = 0; 
string answer; 
string converted = convert(original); 
int len = converted.length(); 

if (len % 2 == 0){ 
    for (int i = 0; i < len - 1; i++){ 
     int lower(i),upper(i+1); 
     while (lower >= 0 && upper <= len && converted[lower] == converted[upper]){ 
      lower -= 1; 
      upper += 1; 
     } 
     string s = converted.substr(lower+1,upper-lower-1); 
     if (s.length() > longest){ 
      longest = s.length(); 
      answer = s; 
     } 
    } 
} else { 
    for (int i = 0; i < len; i++){ 
     int lower(i), upper(i); 
     while (lower >= 0 && upper <= len && converted[lower] == converted[upper]){ 
      lower -= 1; 
      upper += 1; 
     } 
     string s = converted.substr(lower+1,upper-lower-1); 
     if (s.length() > longest){ 
      longest = s.length(); 
      answer = s; 
     } 
    } 
} 

Sorunlarım sabit yüzden, gayet iyi çalışıyor fakat dönüştürülen dize uzunluğu tek ise. Lütfen yardım et. Ben iki büyük hata görebilirsiniz

Answer 1

: Eğer i için üst/alt işaretçiler initialize olsun

1. i veya i, i + 1 bulmak istediğiniz Palindrome uzunluğunun parite değil bağlıdır Özgün dize Yani (herhangi bir başka optimizasyon olmadan), 0'dan len'e (len-1), tek bir palindrom uzunluğu ve diğeri için bir tane olmak üzere iki ayrı döngüye ihtiyacınız olacaktır.
2. Algoritmalar yalnızca dönüştürülen dizede gerçekleştirilmelidir. Çalışması için ilk önce orijinal dizgiyi dönüştürmeniz gerekir.

bu dizeyi göz önünde bulundurun: geçersiz karakterler hariç en uzun palindrom açıkça abcba olduğunu (^ yasadışı karakterdir), ancak i==2 almak ve teker alt/üst sınırları dışında taşıdığınızda, öldürecekler alt dizesini tanımlayın, dönüşümden sonra bc ve b != c olur, bu nedenle bu palindromun genişletilemeyeceğini kabul edersiniz.

Answer 2

#include <iostream> 
using namespace std; 

int main() 
{ 

string s; 
cin >> s; 
signed int i=1; 
signed int k=0; 
int ml=0; 
int mi=0; 
bool f=0; 

while(i<s.length()) 
{ 
    if(s[i]!=s[i+1]) 
    { 
     for(k=1;;k++) 
      { 
       if(!(s[i-k]==s[i+k] && (i-k)>=0 && (i+k)<s.length())) 
       {    
        break; 
       } 
      else if(ml < k) 
       { 
        ml=k; 
        mi=i; 
        f=1; 
       } 
      } 
    } 
i++; 
} 

i=0; 

while(i<s.length()) 
{ 
    if(s[i]==s[i+1]) 
    { 
     for(k=1;;k++) 
     { 
       if(!(s[i-k]==s[k+1+i] && (i-k)>=0 && (k+i)<s.length())) 
       { 
        break; 
       } 
       else if(ml < k) 
       { 
       ml=k; 
        mi=i; 
       } 
      }      
    } 
    i++; 
} 

if(ml < 1) 
{ 
    cout << "No Planidrom found"; 
    return 0; 
} 

if(f==0) 
{ 
cout << s.substr(mi-ml,2*ml+2); 
} 
else 
{ 
cout << s.substr(mi-ml,2*ml+1); 
} 

return 0; 

} 

@biziclop: Dediğiniz gibi .. 2 döngü yaparken kullandım. eski palindrom dizgisi için biri ve diğeri için. sonunda onu tamir edebildim. önerin için teşekkürler.