int KMP(char* s)
{
    int res = 0;    // contatore corrispondenze testo-pattern
    for (int i = 0, j = 0; i < N;) {
        if (s[i] == pattern[j]) {   // c'è corrispondenza tra un carattere del testo e
                                    // uno del pattern
            i++, j++;       // passiamo al carattere successivo
            if (j == M) {   // se j == M significa che è stata troavata una corrispondenza
                            // di lunghezza M, ovvero è stato trovato il pattern all'interno del testo
                res++;
                j = lps[j - 1];     // aggiorniamo j saltando i caratteri che a priori corrispondono
            }
        }
        else {
            if (j) j = lps[j - 1];  // se j != 0 aggiorniamo j saltando i caratteri che a priori
                                    // corrispondono per trovare una eventuale corrispondenza in
                                    // un punto precedente del pattern
            else i++;               // se j == 0 non c'è alcuna corrispondenza, quindi andiamo al
                                    // carattere successivo
        }
    }
    return res;
}

void init_LPS_array() {
    lps[0] = 0;
    for (int i = 1, j = 0; i < M;)
        if (pattern[i] == pattern[j])   // corrispondenza trovata all'interno del pattern
            lps[i++] = ++j;
        else {
            if (j) j = lps[j - 1];  //  se j != 0 aggiorno j (la corrispondenza potrebbe trovarsi
                                    //  in una porzione precedente del pattern
            else lps[i++] = 0;      //  non c'è corrispondenza
        }
}