Hello world c++

Aiuto
1

https://pastebin.com/KbC98GaL

con questo programma prendo 50/100 e non capisco come poterlo ottimizzare, ho provato con while(true) e find ma ci mette perfino di più. Qualcuno può darmi una mano?

2

La stringa in input può avere 1 000 000 di caratteri e un O(N^2) va in timeout.
Dovresti cercare una soluzione lineare.
Suggerimenti:

  • Una volta che hai capito che sei in presenza di “hello” o di “world” puoi spostare l indice di 4 o 5 posizioni.

  • Esiste la funzione compare della stringa che ti permette di confrontarla con altre in maniera molto più semplice. Ti suggerisco di leggere la documentazione per più dettagli

for(int i=0;i<a.length();i++){
        if(a.compare(i,5,"hello") == 0){    	
            for(int k=i+5;k<a.length();k++){
                if(a.compare(k,5,"world") == 0)
                    risultato++;
            }
        }      
    }
1 Mi Piace
4

Grazie per avermi insegnato la funzione compare ma in ogni caso il tempo di esecuzione non cambia, continua a darmi 50/100 :confused:

5

Perché la complessità non è cambiata, rimane sempre O(N^2).
Devi trovare una soluzione lineare O(N).
Prova a cambiare modo di contare, sapendo che ogni volta che trovi un “world” non puoi combinarlo con gli “hello” successivi cosa ti conviene fare ?

1 Mi Piace
6

Saltarlo(?)

()))))()(

7

Saltarlo va bene, ma dopo aver calcolato quante sottostringhe genera.
Prova a pensare a questo caso di test e segnati quante sottostringhe generi per ogni parola :
world hello hello hello world hello world world hello world
Cosa noti ?

8

Credo di aver capito: in pratica, con un contatore, conto quante volte compare la parola “hello” e nello stesso tempo, quando trovo la parola “world” la moltiplico per il valore che ha in quel momento il contatore e lo aggiungo al risultato

1 Mi Piace
9

O meglio, lo sommo, non lo moltiplico(anche se il risultato è lo stesso)

10

Esatto, ora non dovresti aver problemi per fare 100/100. Ti ricordo di usare i long long come descritto nelle note del problema.

1 Mi Piace
11

https://pastebin.com/f82HxPYt

Mi viene 50/100 ma stavolta per colpa di un output

12

Il bello che ti ho anche ricordato di usare i long long LOL
La variabile risultato è ancora un int.

1 Mi Piace
13

Diavolo, le avevo cambiate, forse devo aver usato undo e infine me ne sono scordato:sweat:

2 Mi Piace