fork download 
  1. /*
  2.  * Rezolvarea naiva in N^3.
  3.  *
  4.  * Se putea si mai rapid in N^2 folosind doua cozi. In prima bagam primul caracter si in a doua urmatorul.
  5.  * Apoi pentru a creste lungimea bagam in prima coada primul caracter din a doua coada, iar aceasta
  6.  * primea inca 2 caractere (daca mai existau). La fiecare scoatere-bagare se actualizau doua numere
  7.  * pe post de hashuri. Aceste doua hashuri se comparau in O(1) folosind `==` astfel scutind inca o dimensiune.
  8.  *
  9.  * Calcularea numerelor se facea astfel: se scadea din caracterul curent caracterul 'A' ('A' < 'a') si se aduna la suma.
  10.  * Inainte de adunare suma era inmultita cu 100 (pentru evitarea coliziunilor evidente) pentru prima suma (specifica primei cozi).
  11.  * Din a doua suma se scadea valoarea primului caracter si se adunau pe rand primul caracter la puterea `p` si al doilea la puterea `p` + 1.
  12.  * Unde `p` reprezinta numarul de caractere din prima coada - 1 (adica jumatate de palindrom).
  13.  *
  14.  * Deoarece sumele sunt foarte mari se facea modulo cu o constanta destul de mare si pentru evitarea coliziunilor mai putin evidente
  15.  * se foloseau vreo `k` constante (3-6) diferite pentru a compara sumele intre ele, astfel crescand acuratetea.
  16.  * Complexitatea finala devenea O(KN^2).
  17.  */
  18.  
  19. #include <iostream>
  20. #include <string>
  21. using namespace std;
  22.  
  23.  
  24. int maxPal; // dimensiunea maxima
  25. string str, pal; // sirul sursa, palindromul maxim
  26.  
  27.  
  28. void solve()
  29. {
  30.     /**
  31.      * Pentru fiecare pozitie si lungime se genereaza o subsecventa
  32.      * ce se compara cu ea insasi pornind din extremitati.
  33.      * Probabil daca se genereaza si inversul acesteia dureaza ceva mai mult
  34.      * chiar daca complexitatea teoretica ramane aceeasi.
  35.      */
  36.     for (int pos = 0; pos < str.size(); ++pos) {
  37.         for (int len = 1; len <= str.size() - pos; ++len) {
  38.             string sub = str.substr(pos, len);
  39.             bool isPal = true;
  40.             for (int i = 0; i < len / 2 && isPal; i++) {
  41.                 if (sub[i] != sub[len - i - 1]) isPal = false;
  42.             }
  43.             if (isPal && len > maxPal) {
  44.                 maxPal = len;
  45.                 pal = sub;
  46.             }
  47.         }
  48.     }
  49. }
  50.  
  51.  
  52. int main()
  53. {
  54.     cin >> str;
  55.     solve(); // rezolvam
  56.     cout << pal;
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0.02s 2860KB
comments (?)
stdin 
ThesampletextthatcouldbereadedthesameinbothordersArozaupalanalapuazorA
stdout 
ArozaupalanalapuazorA
https://ideone.com/Pl3zA
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!