836 Palindrom

[•astronomy]

Aici puteti discuta despre problema Palindrom.

[•florin_marius90]

salut! vreau si eu sa stiu care ar fii solutia optima la aceasta problema multumesc

[•gabor_oliviu1991]

O(N^2) cel mai nefavorabil caz. Mai poti optimiza totusi.

PS: Vor aparea solutiile oficiale?

[•florin_marius90]

imi deasheshte cu 0.5 secunde... iau decat 5 puncte plus ca la al 2 lea test imi apare ' incorect' , in rest depasheste tipul ......oare ce oi fii scapat din vedere....
 PS: cum ajung la arhiva de probleme de bac ?

[•Mishu91]

La Palindrom2 intra O(N²).
Aici ai nevoie de o solutie in O(N)

[•gabor_oliviu1991]

Ah da scuze. Si totusi solutia in O(n)? Un hint ceva...

[•Mishu91]

Pai eu am aflat lungimea celui mai lung palindrom care contine ultimu caracter din sirul dat, iar apoi am adaugat la spate primele (N - acea lungime) caractere din sir

[•florin_marius90]

la fel am facut si eu si totushi nu se incadreaza in timp .. depasheste cu 0.05..... am facut programu in pascal . o fii de la pascal???

[•sima_cotizo]

depasheste cu 0.05.....

S-a mai discutat asta: programul vostru este oprit cu 0.05s dupa ce ati depasit limita. Daca ar fi fost lasat sa ruleze pana isi termina treaba, e posibil sa fi sarit cu mai mult de limita. Ganditi-va ce ar fi daca ar fi lasat sa ruleze pana la capat un program care intra in ciclu infinit

[•gh09]

De ce s-a scos problema din arhiva?

[•razyelx]

cand apar solutiile oficiale? sau macar spuneti-mi se poate folosi kmp la problema asta a.i. sa scot 100?

[•sima_cotizo]

http://infoarena.ro/grigore-moisil-2009/solutii#palindrom

[•razyelx]

iau 55 pct cu incorect pe restul.

Cod:

if(q == n-i){
	if(q > l){l = q; unu = 0; doua = 1;}
		q = pi[q];
	}
if(q == n-i+1){
	if(q > l){l = q; unu = 1; doua = 0;}
		q = pi[q];
}

in KMP pun doar acele doua conditii, si ma folosesc de varibila l pentru a afisa palindromul. variabilele unu si doua reprezinte nr de varfuri. Pe exemplele mele merge, mai sunt conditii?

[•Marius]

Testul 8 a fost înlocuit şi am reevaluat sursele.

[•mening12001]

Cod:

#include<iostream.h>
#include<fstream.h>
#include<string.h>
int main()
{char a[200001],b,c[200001];
long i,k=0;
ifstream f("palindrom.in");
ofstream g("palindrom.out");
f.getline(a,200000);
i=strlen(a)-1;
b=a[i-1];
while(i!=0)
	{if(a[i]!=b)
		i=0;
	else
		{k++;
	i--;}
	}
if(k==0)
	{strcpy(c,a);
	strcpy(a+strlen(a)-1,a+strlen(a));
strcat(c,strrev(a));
g<<c;}

else
	{strcpy(c,a);
strcpy(c+strlen(c)-k+1,c+strlen(c));
	strcpy(a+strlen(a)-k,a+strlen(a));
strcat(c,strrev(a));
g<<c;
	}

return 0;}

care este problematica totusi...?
dc apare aceasta inexplicabila eroare?
va multumesc

Editat de admin: Foloseste tagul "code" cand postezi surse.

[•SpiderMan]

Din cate stiu si din ceea ce am citit pe net functia strrev nu este in bibliotecile originale , adica doar in limbajele care au functii "optionale", cum ar fi Code::Blocs, dar in MinGW Developer Studio , adica si pe evaluatorul infoarena, nu exista. De accea iti sugerez sa implementezi functia de mana  
[LE] Am gasit un exemplu de reverse, o sa-l postez, sper sa te ajute

Cod:

#include <iostream> 
#include <cstring> 
using namespace std; 
 
int main() 
{ 
  char str[] = "this is a test"; 
  char *start, *end; 
  int len; 
  char t; 
 
  cout << "Original: " << str << "\n"; 
   
  len = strlen(str); 
 
  start = str; 
  end = &str[len-1]; 
 
  while(start < end) { 
    // swap chars 
    t = *start; 
    *start = *end; 
    *end = t; 
 
    // advance pointers 
    start++; 
    end--; 
  } 
 
 
  cout << "Reversed: " << str << "\n"; 
  return 0; 
}

[•toni2007]

Din cate stiu si din ceea ce am citit pe net functia strrev nu este in bibliotecile originale , adica doar in limbajele care au functii "optionale", cum ar fi Code::Blocs, dar in MinGW Developer Studio , adica si pe evaluatorul infoarena, nu exista. De accea iti sugerez sa implementezi functia de mana 
[LE] Am gasit un exemplu de reverse, o sa-l postez, sper sa te ajute

De cand sunt Codeblocks si Mingw Studio limbaje ?

[•SpiderMan]

Am zis limbaje si am pus "optionale", deci eu cred ca se intelege ca e IDE ... 

[•alexandru92]

adica doar in limbajele care au functii "optionale", cum ar fi Code::Blocs, dar in MinGW Developer Studio

Code::Blocks si MinGW nu contin nici o functie optionala, asta depinde de compilatorul si versiunea( de compilator ) folosita.
strrev este depreciated, la fel ca si itoa.
Pentru strrev exista reverse din STL

Cod:

#include <algorithm> 
//s-sirul
n=strlen(s);
reverse( s, s+n ); //reverse actioneaza pe intervalul [ begin, last ) 

[•wefgef]

SpiderMan, tu chiar nu vrei sa intelegi, sau te prefaci?

E a nu stiu cata oara cand trebuie sa atrag atentia pe forum ca MinGW Developer Studio si Code::Blocks nu pot compila/rula surse.

[•SpiderMan]

SpiderMan, tu chiar nu vrei sa intelegi, sau te prefaci?

E a nu stiu cata oara cand trebuie sa atrag atentia pe forum ca MinGW Developer Studio si Code::Blocks nu pot compila/rula surse.

Ce vrei sa zici cu asta ? Adica da, nu pot compila singure, dar au incorporate un program care face asta ....

[•alexandru92]

Ce vrei sa zici cu asta ? Adica da, nu pot compila singure, dar au incorporate un program care face asta ....

Vrea sa zica ca MinGW/ Code::Blocks sunt niste unelte care te ajuta sa redactezi, compilezi sau sa faci un debug intr-un mod cat mai simplu si placut. Cel care face toata munca din spatele acestor operatiuni este compilatorul , "MinGW/ Code::Blocks sunt doar interfetele"

[•spatarel]

Vă rog să adăugați și testul:

acdbdbacabdca

cu raspunsul corect:

acdbdbacabdcacdbacabdbdca

deoarece am observat că există o sursă (643532) care a obținut 100p, deși pică acest test.

Vă mulțumesc.

[•BoSs_De_BosS]

.... la problema asta iei 100 si daca faci numa pentru palindroame impare 
trebuie modificat ori enuntul ori testele 

[•repp4radu]

Daca a rezolvat cineva problema asta cu algoritmul lui Manacher, as avea nevoie de putin ajutor. Iau doar 25 de puncte cu TLE, desi teoretic ar trebui sa intru lejer in limita de timp.

LE Uitam sa updatez centrul celui mai extins palindrom 

Problem solved thanks to Tudor Tiplea