Metro 70/100 Timeout

Non riesco a superare il subtask 2 e il 5 per timeout. Immagino che il problema sia dato dal mio modo abbastanza grezzo di contare le ripetizioni di una stringa in un altra. Consigli ? Ho provato a cercare se esistono algoritmi appositi per questo compito ma non ho trovato nulla <.<
Ecco Il mio coidce per chi volesse vederlo --> codice

In realtĂ  ci sono numerosi algoritmi e strutture per fare string matching :slight_smile:
In questo caso, il più immediato penso sia Rabin-Karp, volendo però puoi usare anche KMP.

2 Mi Piace

Grazie, sono riuscito a fare 100 ^-^
Non ho utilizzato i codici che hai linkato ma ho trovato questa versione che ha risolto il mio problema kmp
Con il rabin-karp ho pure peggiorato i tempi stranamente O.o

EDIT: Ho pure fatto il miglior tempo LOL

1 Mi Piace

Consiglio: non limitarti a copiare il codice, ma cerca di capire e imparare il ragionamento che c’è dietro perché potrebbe tornare utile altre volte :wink:

1 Mi Piace

Sicuro che il Rabin-Karp possa dare 100? Io con un’implementazione quasi identica a quella che hai linkato ottengo 70 :confused:

1 Mi Piace

Succede perché l’implementazione di geeksforgeeks non si “accontenta” del fatto che gli hash corrispondano, ed ogni volta che succede ricontrolla tutta la stringa.
Puoi evitare di fare ciò, se non ci sono collisioni dovrebbe funzionare.

1 Mi Piace

GiĂ  provato, funziona su tutti i testcase tranne il 9 che da output not correct :confused:
Avevo pensato di fare un’implementazione a parte solo per il subtask 2 dato che viene specificato che le porte vengono aperte sempre a sinistra ma credo sia cheating quindi non mi va molto a genio.

1 Mi Piace

Prova a cambiare numero primo, magari con uno piĂą elevato.

1 Mi Piace

Neppure con 734774299560345449 ottengo 100/100, mi sa che dovrò utilizzare un altro algoritmo.

1 Mi Piace

KMP is the way :slight_smile:

Perdonami, non avevo controllato l’implementazione di Geeks for Geeks - ma l’idea è la stessa, a patto di prestare un po’ di fiducia all’hashing :slight_smile:

Anche se hai già risolto, può essere interessante sfruttare questo problema per imparare anche KMP, nonostante l’hashing sia spesso più flessibile e pratico :wink:

Alla fine ho risolto con KMP. In realtĂ  anche Rabin-Karp dava 100/100 solo che nelle assunzioni stava scritto N <= 10 000 000 mentre io consideravo N < 10 000 000. :cry:

1 Mi Piace

Io avevo implementato un KMP ma dĂ  sia TLE sia output sbagliati.
Allego il codice… qualche buon’anima che mi controlli se l’implementazione del KMP è corretta? Grazie in anticipo.

int arr[10000050], n, m; // size m
vector<bool> p_letters;

void build_array()
{
    int j=0, i=1;
    arr[0] = 0;
    while(i < (int)p.size())
    {
        if(p[i] == p[j]){
            arr[i] = j+1;
            i++;
            j++;
        }
        else
        {
            if(j==0)
            {
                arr[i] = 0;
                i++;
                continue;
            }
            j = arr[j-1];
        }
    }
    return;
}

int find_pattern_in_text(int from)
{
    int j=0; // index nel pattern
    for(int i=from; i<n && j<m; i++)
    {
        if(t[i] == p[j]) j++;
        else{
            if(j==0) // because arr[0] is 0, and if it arrives here it means that p[0] is different from t[i] so it must go on
                continue;
            i--;
            j=arr[j];
        }
        if(j==m)
            return i-p.size()+1;
    }
    return -1;
}

Ciao, la tua implementazione non mi sembra corretta al 100%, (non capisco perchè fai restituire i-p.size()+1 quando j==m. Ti lascio questa implementazione che a me ha dato 100 e mi sembra anche leggermente più breve da scrivere in particolare per quanto riguarda la costruzione dell’array. https://pastebin.com/iLEBL014

1 Mi Piace

a dir la verità era una mia implementazione che ho copiato e incollato (nel codice precedente volevo stampare l’indice a cui il pattern compariva nel testo). Appena ho un po’ di tempo guardo l’implementazione che mi hai linkato.
Grazie!

Un messaggio è stato spostato in un nuovo argomento: Errore grader metro

1 Mi Piace