Execution timed out Parser HTML (html)

Aiuto
1

(Mi scuso in anticipo per gli accenti, sto usando una tastiera americana)

Nonostante sia riuscito ad ottenere un programma che dia il risultato corretto, sto avendo dei problemi negli ultimi due Testcase a causa dell’errore “Execution timed out”. Ne capisco perfettamente il significato, il mio problema, e’ che non capisco come ottimizare il mio codice per ridurre da O(N^2) ad O(N). Questo e’ il codice:

#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

int main()
{
	ifstream input("input.txt");
	ofstream output("output.txt");

	int N;
	input >> N;
	string line;
	int result = N;

	vector <string> file;
	while(getline(input, line)) {
		file.push_back(line);
	}

	for (int i = 0; i < file.size(); i++) {
		while (file[i].find("&amp;") != string::npos) {
			file[i].replace(file[i].find("&amp;"), 5, "&");
			result -= 4;
		}
	}

	output << result;
	for (auto line : file) {
		output << line << "\n";
	}

	input.close();
	output.close();
	return 0;
}

avrei bisogno davvero di capire come si crea un algoritmo molto efficiente, dato che, nella maggior parte dei problemi, cio’ che mi impedisce di raggiungere un certo punteggio e’ proprio l’efficienza dell’algoritmo.

Vorrei anche aggiungere che supero il tempo limite di 0.066 e 0.099 secondi

2

Le funzioni std::string::find e std::string::replace funzionano entrambe con complessità O(N) di tempo. Eseguite per ogni carattere portano la complessità totale a O(N^2) . Per ridurre la complessità potresti migliorare la ricerca e non usare la funzione replace per modificare la stringa. Considera il terzo caso d’ esempio: una volta trovato la prima occorrenza da modificare, dove si potrebbe trovare la successiva?

3

ripensandoci, dovrei memorizzare il valore di find all’interno di una variabile, in modo da non doverlo calcolare sia nell’if che nel replace. Dopo provo. Grazie del suggerimento!

Edit: dopo aver provato con una variabile, ho scoperto che mi da Execution timed out su tutti. Provo qualche altro modo.

Edit 2: sono riuscito a capire l’errore: oltre a salvare il valore in una variabile, faccio partire la ricerca dall’ultimo punto in cui ho trovato un riscontro di “&” cosi’ da non dover cercare in tutta la stringa ogni volta. Con questo ragionamento “quasi” TUTTI i tempi sono scesi: il penultimo e’ passato da 1,100 secondi a 0,097 secondi. l’unico problema? L’Ultimo testcase supera lo stesso un secondo: 1,100 secondi circa…

4

Utilizzi sempre la funzione replace? Se si, dovresti farne a meno.

Prova a modificarla a “mano”.