[C/C++]Palindrome

[Rfd]

Timus Online Judge. Problem 1297

//#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
string s1, s2, s3, smax;
int i, j, n, m, pos, lol, maxt;
int main ()
{
	cin>>s1;
	maxt=0;
	for (i=1;i<=s1.length();i++)
		for (j=0;j<s1.length();j++)
		{
			s2=s1.substr(j, i);
			s3=s2;
			reverse(s3.begin(),s3.end());
			if (s2==s3)
			{
				pos=s1.find(s2);
				if (pos!=string::npos)
				{
					lol=s2.length();
					if (lol>maxt)
					{
						maxt=lol;
						smax=s2;
					}
				}
			}
		}
		cout<<smax;
		system("pause");
		return 0;
}

Pe acest cod C++ am TLE (Time limit exceeded) pe testul 15. Am facut acest topic pentru a cere sfaturi in legatura cu solutia problemei.

Va multumesc!

[cmiN]

Voi chiar aveti fetishuri cu probleme cu palindroame ? Ca si la sectiunea cu challengeuri se tot postau diverse chestii similare, nu am vazut niciodata atata interes si surse pentru ceva atat de banal -,-.

Eu am luat Accepted cu 0.68s.

Ideone.com | Online C++ Compiler & Debugging Tool

/*
 * Rezolvarea naiva in N^3.
 *
 * Se putea si mai rapid in N^2 folosind doua cozi. In prima bagam primul caracter si in a doua urmatorul.
 * Apoi pentru a creste lungimea bagam in prima coada primul caracter din a doua coada, iar aceasta
 * primea inca 2 caractere (daca mai existau). La fiecare scoatere-bagare se actualizau doua numere
 * pe post de hashuri. Aceste doua hashuri se comparau in O(1) folosind `==` astfel scutind inca o dimensiune.
 *
 * Calcularea numerelor se facea astfel: se scadea din caracterul curent caracterul 'A' ('A' < 'a') si se aduna la suma.
 * Inainte de adunare suma era inmultita cu 100 (pentru evitarea coliziunilor evidente) pentru prima suma (specifica primei cozi).
 * 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.
 * Unde `p` reprezinta numarul de caractere din prima coada - 1 (adica jumatate de palindrom).
 *
 * Deoarece sumele sunt foarte mari se facea modulo cu o constanta destul de mare si pentru evitarea coliziunilor mai putin evidente
 * se foloseau vreo `k` constante (3-6) diferite pentru a compara sumele intre ele, astfel crescand acuratetea.
 * Complexitatea finala devenea O(KN^2).
 */


#include <iostream>
#include <string>
using namespace std;


int maxPal; // dimensiunea maxima
string str, pal; // sirul sursa, palindromul maxim


void solve()
{
    /**
     * Pentru fiecare pozitie si lungime se genereaza o subsecventa
     * ce se compara cu ea insasi pornind din extremitati.
     * Probabil daca se genereaza si inversul acesteia dureaza ceva mai mult
     * chiar daca complexitatea teoretica ramane aceeasi.
     */
    for (int pos = 0; pos < str.size(); ++pos) {
        for (int len = 1; len <= str.size() - pos; ++len) {
            string sub = str.substr(pos, len);
            bool isPal = true;
            for (int i = 0; i < len / 2 && isPal; i++) {
                if (sub[i] != sub[len - i - 1]) isPal = false;
            }
            if (isPal && len > maxPal) {
                maxPal = len;
                pal = sub;
            }
        }
    }
}


int main()
{
    cin >> str;
    solve(); // rezolvam
    cout << pal;
    return 0;
}

P.S.: Macar citeste si comentariile inainte sa dai copy paste .

Edited April 5, 2012 by cmiN

[ionut.hulub]

acceptat cu timp de executie de 0.031 secunde.

#include <iostream>
using namespace std;

bool palindrom(char* s, int a, int  {
	int aux = a+(b-a)/2;
	for (int i = a; i <= aux; i++)
		if (s[i] != s[b+a-i])
			return 0;
	return 1;
}

int main() {
	char s[1001];
	int n = 0, i, j, aux;
	cin>>s;
	n = strlen(s);
	n--;
	for (i = 0; i <= n; i++) 
		for (j = 0; j <= i; j++) /*selecteaza cel mai mare subsegment inca netestat(indicii de inceput si de sfarsit)*/
			if(palindrom(s, j, n-i+j)) { /*verifica daca subsegmentul este palindrom*/
				aux = n-i+j;
				while(j<=aux)
					cout<<s[j++]; /*daca este palindorm, afiseaza subsegmentul apoi opreste executia programului*/
				return 0;
			}
	return 0;
}

merge pe acelasi principiu cu cel postat de cmiN doar are avantajul ca testeaza intai substrigurile cele mai mari care inca nu au fost testate. in felu asta, in momentu in care gasesti un palindrom poti sa fii sigur ca e cel mai mare si nu mai e nevoie sa mai testezi si restu posibilitatilor.

ar mai putea fi aduse ceva imbunatatiri dar nu prea merita efortul.

Edited April 8, 2012 by NemesisITSC

[Rfd]

Va multumesc mult!