Scusate mi potreste dare una mano a capire dove sbaglio nel problema “insegna”,avendo la febbre ora(non è corona state tranquilli) non riesco ad essere tanto lucido mi potreste aiutare,vi lascio di seguito il codice:
#include <bits/stdc++.h>
using namespace std;
int main(){
ofstream out("output.txt");
ifstream in("input.txt");
long long int N;
in>>N;
string s,s1,s2,s3;
in>>s>>s1;
long long int i=0;
bool A=false;
while(N/2-i!=0 && A==false){
s2=s.substr(0,N/2-i);
s3=s.substr(N/2-i,N-(N/2+i));
if(s1.find(s2)!=-1 && s1.find(s3)!=-1){
A=true;
}
else{
i++;
}
}
while(N/2+i!=N && A==false){
s2=s.substr(0,N/2+i);
s3=s.substr(N/2+i,N-(N/2-i));
if(s1.find(s2)!=-1 && s1.find(s3)!=-1){
A=true;
}
else{
i++;
}
}
if(A==true){
out<<1;
}
else{
out<<0;
}
}
Se vi servono dei chiarimenti sulla mia idea chiedete,grazie in anticipo.
non ti so dire esattamente quale sia l’errore, se vuoi un hint ti posso dire che io l’ho risolto con un piccolo escamotage usando una sola data structure e un controllo.
ho inserito le due stringhe(char per char) in 2 multiset distinti,(nel caso non lo sapessi puoi confrontarli con un if(multi1 == multi2)) se possiedono gli stessi elementi restituisce 1 altrimenti 0
in un set non ci possono essere ripetizione di caratteri o interi etc… nel multiset puoi invece avere ripetizioni di valori inseriti. entrambi vengono sortati all’inserimento di un valore.
esempio:
hai un array {3,4,4,2}
se inserisci l’array nel set avrai {2,3,4}
se lo inserisci nel multiset avrai {2,3,4,4}
(esistono anche gli unordered_set e unordered_multiset, penso tu possa intuire la loro funzione)
Se vi può interessare esiste anche una soluzione in O(N), in pratica quando devo capire se arolap è una rotazione di parola mi basta cercare arolap nella stringa parolaparola, questo può essere fatto usando KMP o Rabin-Karp (dipende dalla vostra religione).
Comunque non ho capito la soluzione di @alep, così non controlla solo che una sia l’anagramma dell’altra?
La risposta dovrebbe essere 0, il tuo codice dovrebbe rispondere 1, mi sembra assurdo che non ci sia un tc del genere tra gli input.
Anyway se vuoi sbizzarrirti con gli anagrammi c’è un problema carino (nel quale tra l’altro credo che un multiset non sia abbastanza efficiente)
wow, mi era sorto qualche dubbio quando sottoposi ma non credevo fosse veramente sbagliata, comunque proverò a vedermi quel problema che mi hai consigliato(nonstante mi sia ripromesso di lasciar stare i problemi con le stringhe), grazie mille
Ma figuati, felice di aiutare (comunque per me i problemi con le stringhe non sono per niente male , a meno che non richiedano di implementare un suffix tree obv)
Eh purtroppo non conosco nel dettaglio le implementazioni, tuttavia con N abbastanza grandi is_permutation comincia a perdere molto, avendo complessità N^2 contro la NlogN dell’inserire gli elementi nel multiset.
Comunque se stai cercando la velocità un multiset è eccessivo, basta sortare le stringhe con std::sort(stringa.begin(),stringa.end()) e poi compararle (complessità sempre NlogN ma con fattori costanti minori), oppure potresti usare algoritmi più efficienti quando l’alfabeto è piccolo, come il counting sort O(N + grandezza\ alfabeto).
KMP e Rabin-Karp sono entrambi lineari quindi O(N), is_permutation()
è O(N^2) quindi con un time-limit di 1s KMP e Rabin-Karp si fermano quando N vale qualche milione, con O(N^2) ti fermi a qualche miglialia.
(nel quale tra l’altro credo che un multiset non sia abbastanza efficiente)
, a meno che non richiedano di implementare un suffix tree obv)