[Algoritmi] Estensione algoritmo di Knuth-Morris-Pratt

[ZfreS]

Buonasera. Ho implementato l'algoritmo di Knuth-Morris-Pratt e volevo estenderlo per gestire il caso in cui il pattern è una rotazione ciclica di un'altra stringa. Ho pensato a tale scopo di creare una copia della stringa. Mi piacerebbe però poter solamente modificare la funzione insuccesso per rilevare quella proprietà. Sapreste dirmi se ciò è possibile ed eventualmenete come poterlo fare? Grazie!

Codice:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int *insuccesso(char pat[])
{
    int n = strlen(pat);
    int i;
    int *insuc = (int *) malloc(n * sizeof(int) );
    insuc[0] = -1;

    for(int j = 1; j < n - 1; j++)
    {
        i = insuc[j - 1];

        while(pat[j] != pat[i + 1] && i >= 0)
            i = insuc[i];

        if(pat[j] == pat[i + 1])
            insuc[j] = i + 1;
        else
            insuc[j] = -1;
    }

    return insuc;
}

int KMP_match(char stringa[], char pat[])
{
    int *insucc = insuccesso(pat);
    int i = 0;
    int j = 0;
    int lenS = strlen(stringa);
    int lenP = strlen(pat);

    while(i < lenS && j < lenP)
    {
        if(stringa[i] == pat[j])
        {
            i++;
            j++;
        }

        else if (j == 0)
                i = i++;
        else
            j = insucc[j - 1] + 1;
    }

    free(insucc);

    if(j == lenP)
        return i - lenP;
    else
        return -1;
}


[apatriarca]

Prima di tutto sto pensando al problema per la prima volta solo ora, quindi non ho modo di darti una soluzione certa al tuo problema.

Prima di tutto credo sia importante osservare che nel caso in cui stai testando tutte le rotazioni cicliche di una stringa, non puoi semplicemente scorrere la stringa dall'inizio alla fine ma devi considerare anche tutte le sue rotazioni. Il match potrebbe insomma per esempio partire dal terzo carattere. Ancora peggio, potresti avere più posizioni per cui il match iniziale sia valido. Sinceramente partirei dal convertire il tuo pattern in un NFA e usare un algoritmo come quello descritto qui per fare il confronto tra stringa e pattern. A questo punto puoi usare una tabella come quella in KMP per fare i salti. Ovviamente con un NFA non hai bisogno davvero di fare salti in quel modo perché puoi implementare l'algoritmo in modo che consideri partenze ad ogni nuovo carattere.

Dopo una breve ricerca ho comunque trovato anche l'algoritmo di Aho-Corasick e quello di Commentz-Walter che sono stati pensati per cercare una lista di stringhe invece di una sola come per il KMP e che sono quindi direttamente applicabili al tuo caso.

[vict85]

Se introduci la possibilità di rotazioni, allora in caso di insuccesso potresti ricominciare da qualsiasi ripetizioni delle sotto-stringhe della parte trovata finora.

Supponi per esempio tu abbia "ababf", con "f" sbagliato. A questo punto potresti ripartire da ogni ripetizioni delle stringhe "abab", "bab", "ab" e "b" nella stringa pattern. Mi viene quindi difficile pensare che tu possa mantenere la linearità, sia di tempo che di spazio, della funzione insuccesso e probabilmente andresti anche a moltiplicare per la lunghezza del pattern anche la complessità della funzione di match.

Se questo è vero e non solo una mia impressione, allora sarebbe più performante un approccio del tipo (scritto in uno pseudocodice a caso):

Codice:

insucc = insuccesso(pat)
for i in [0, len(pat)] :
    matched_index = match(stringa, insucc)
    if( matched_index != len(string) ) return matched_index;
    aggiorna_insuccesso( insucc, pat)
end for

dove aggiorna_insuccesso è una funzione che aggiorna l'array insuccesso per una rotazione verso sinistra.