E' da parecchio che sto cercando di risolvere questo problema ma senza successo. La mia idea è questa: Scorro la stringa e per ogni posizione cerco la piu lunga stringa di fibonacci che parte da qui. Per fare questo creo sul momento una stringa di fibonacci di lunghezza adeguata( "a") e la confronto con la stringa che sto verificando. Notare che una stringa di fibonacci è a sua volta composta da stringhe di fibonacci di lunghezza cresciente : 1,1,2,3,5,8 ecc..., proprio come i numeri di fibonacci : a b a ab aba abaab abaababa.
Io sfrutto cio andando a verificare ogni volta la parte che si aggiunge che deve essere uguale alla mia appena generata stringa "a". L'algoritmo è abbastanza complesso da spiegare e mi scuso per ciò. Spero che guardando il codice riusciate a capire meglio.
A me questo codice/algoritmo sembrerebbe corretto, a massimo che abbia problemi di TME, ma in realtà mi totalizza solo 36 punti, prendendo WA negli altri test cases, cosa che non mi spiego...spero mi possiate illuminare, ci sto soffrendo sopra da troppo!
int N,sol=1,indI,indF;
string fib="a",S;
vi fibNum;
int main() {
ifstream in; ofstream out;
in.open("input.txt"); out.open("output.txt");
in>>N>>S;
fibNum.push_back(1); fibNum.push_back(2); //Creo un vettore con tutti i numeri di fibonacci fino a una lunghezza appena superiore
for(int i=2;i<30;i++) // a quella massima della stringa
fibNum.push_back(f[i-1]+f[i-2]);
for(int i=0;i<N-1;i++){
char t=S[i],t2=S[i+1]; //Ad ogni passo considero carattere corrente e quello successivo e //provo a fare partire
//la stringa di fibonacci da qui
if(t==t2)
continue;
string a="",b="";
a += t; b += t2;
int shift = 0, k = 0, end = i+1, solTemp = 2;
while( (i + 2 + shift + fibNum[k]) <= S.length() && S.compare( i + 2 + shift, fibNum[k], a)==0){
end = i + 2 + shift + fibNum[k];
shift += fibNum[k++];
a += b;
b = a;
}
if(k>0) solTemp = 2+shift; //shift+2 rappresenta la lunghezza perche a shift viene aggiunto sempre l'ultimo fib number e alla fine ne possedera uno in piu del dovuto
if(solTemp > sol){
sol = solTemp;
indI = i;
indF = i+solTemp-1;
}
}
out<<indI+1<<" "<<indF+1;
in.close(); out.close();
return 0;
}
//25
