Buongiorno a tutti, è da un po che sto provando a risolvere questo problema. L’esempio di input presente nello statement mi da l’output corretto, e anche qualche test fatto da me sembra funzionare. Tuttavia nessuno dei test case delle sottoposizioni risulta corretto (non ci sono problemi di tempo o memoria).
Probabilmente mi sto perdendo qualcosa, ma veramente non riesco a capire cosa sia. C’è un vecchio topic su questo problema, ma non mi è molto di aiuto.
Allego il codice.
#include <bits/stdc++.h>
using namespace std;
string fib;
int N;
int fibseq(int inizio){
vector <string> temp;
temp.push_back(fib.substr(inizio, 1));
temp.push_back(fib.substr(inizio+1, 1));
int lunghezza=2, index=2, indexfib=inizio+2;
bool fatto = false;
while((indexfib+lunghezza<N-1) && (temp[index-1]+temp[index-2])==(fib.substr(indexfib, lunghezza))){
temp.push_back(temp[index-1]+temp[index-2]);
index++;
indexfib+=(temp[temp.size()-1].size());
lunghezza = (temp[index-1].size()+temp[index-2].size());
fatto = true;
}
if(fatto)
return indexfib;
else
return inizio+2;
}
int main(){
cin >> N;
cin >> fib;
//cout << fib;
int maxinizio = 0;
int maxfine = 1;
for(int i=0; i<N-1; i++){
int fine = fibseq(i);
if((fine-i)>(maxfine-maxinizio)){
maxfine = fine;
maxinizio = i;
}
}
//cout << fib.substr(maxinizio-1, (maxfine-maxinizio)+1) << endl;
cout << maxinizio << " " << maxfine;
return 0;
}