{"id":1421,"date":"2021-08-25T10:34:49","date_gmt":"2021-08-25T10:34:49","guid":{"rendered":"https:\/\/www.coupontoaster.com\/blog\/?page_id=1421"},"modified":"2023-04-28T13:17:40","modified_gmt":"2023-04-28T13:17:40","slug":"introduzione","status":"publish","type":"page","link":"https:\/\/coupontoaster.com\/blog\/introduzione\/","title":{"rendered":"introduzione"},"content":{"rendered":"\n
\n\n\n\n

introduzione<\/p>\n\n\n\n

La corrispondenza delle stringhe \u00e8 un argomento molto importante nel pi\u00f9 ampio dominio dell’elaborazione del testo. Gli algoritmi di corrispondenza delle stringhe sono componenti di base utilizzati nelle implementazioni di software pratici esistenti nella maggior parte dei sistemi operativi. Inoltre, enfatizzano i metodi di programmazione che fungono da paradigmi in altri campi dell’informatica (progettazione di sistemi o software). Infine, svolgono anche un ruolo importante nell’informatica teorica fornendo problemi impegnativi.<\/p>\n\n\n\n

Sebbene i dati vengano memorizzati in vari modi, il testo rimane la forma principale per lo scambio di informazioni. Ci\u00f2 \u00e8 particolarmente evidente in letteratura o linguistica, dove i dati sono composti da enormi corpus e dizionari. Questo vale anche per l’informatica, dove una grande quantit\u00e0 di dati \u00e8 archiviata in file lineari. E questo \u00e8 anche il caso, ad esempio, nella biologia molecolare perch\u00e9 le molecole biologiche possono spesso essere approssimate come sequenze di nucleotidi o amminoacidi. Inoltre, la quantit\u00e0 di dati disponibili in questi campi tende a raddoppiare ogni diciotto mesi. Questo \u00e8 il motivo per cui gli algoritmi dovrebbero essere efficienti anche se la velocit\u00e0 e la capacit\u00e0 di archiviazione dei computer aumentano regolarmente.<\/p>\n\n\n\n

String-matching consiste nel trovare una, o pi\u00f9 in generale, tutte le occorrenze di una stringa (pi\u00f9 generalmente detta pattern<\/em> ) in un testo<\/em> . Tutti gli algoritmi in questo libro restituiscono tutte le occorrenze del modello nel testo. Il modello \u00e8 denotato da x<\/em> =x[0 .. m<\/em> -1]; la sua lunghezza \u00e8 pari a m<\/em> . Il testo \u00e8 indicato con y<\/em> =y[0 .. n<\/em> -1]; la sua lunghezza \u00e8 pari a n<\/em> . Entrambe le stringhe sono costruite su un insieme finito di caratteri chiamato alfabeto<\/em> denotato da \"Sigma\"con dimensione uguale a \"sigma\".<\/p>\n\n\n\n

Le applicazioni richiedono due tipi di soluzione a seconda di quale stringa, modello o testo viene fornita per prima. Algoritmi basati sull’uso di automi o propriet\u00e0 combinatorie di stringhe sono comunemente implementati per preelaborare il pattern e risolvere il primo tipo di problema. La nozione di indici realizzati da alberi o automi viene utilizzata nel secondo tipo di soluzioni. Questo libro indagher\u00e0 solo gli algoritmi del primo tipo.<\/p>\n\n\n\n

Gli algoritmi di corrispondenza delle stringhe del presente libro funzionano come segue. Scansionano il testo con l’aiuto di una finestra la<\/em> cui dimensione \u00e8 generalmente pari a m<\/em> . Prima allineano le estremit\u00e0 sinistre della finestra e il testo, quindi confrontano i caratteri della finestra con i caratteri del modello – questo lavoro specifico \u00e8 chiamato tentativo<\/em> – e dopo un’intera corrispondenza del modello o dopo una mancata corrispondenza spostano<\/em> il finestra a destra. Ripetono di nuovo la stessa procedura finch\u00e9 l’estremit\u00e0 destra della finestra non supera l’estremit\u00e0 destra del testo. Questo meccanismo \u00e8 solitamente chiamato meccanismo della finestra scorrevole<\/em> . Associamo ogni tentativo alla posizione j<\/em> nel testo quando la finestra \u00e8 posizionata suy<\/em> [ j<\/em> .. j + m-1<\/em> ].<\/p>\n\n\n\n

L’ algoritmo Brute Force<\/a> individua tutte le occorrenze di x<\/em> in y<\/em> nel tempo O( mn<\/em> ). I numerosi miglioramenti del metodo della forza bruta possono essere classificati in base all’ordine in cui hanno eseguito i confronti tra caratteri del modello e caratteri di testo e ad ogni tentativo. Si presentano quattro categorie: il modo pi\u00f9 naturale per eseguire i confronti \u00e8 da sinistra a destra, che \u00e8 la direzione di lettura; eseguire i confronti da destra a sinistra generalmente porta ai migliori algoritmi in pratica; i migliori limiti teorici si raggiungono quando i confronti sono fatti in un ordine specifico; infine esistono degli algoritmi per i quali l’ordine in cui vengono effettuati i confronti non \u00e8 rilevante (tale \u00e8 l’algoritmo della forza bruta).Da sinistra a destra<\/a><\/p>\n\n\n\n

L’hashing fornisce un metodo semplice che evita il numero quadratico dei confronti di caratteri nella maggior parte delle situazioni pratiche e che funziona in tempo lineare sotto ipotesi probabilistiche ragionevoli. \u00c8 stato introdotto da Harrison e successivamente analizzato completamente da Karp e Rabin<\/a> .<\/p>\n\n\n\n

Supponendo che la lunghezza del modello non sia pi\u00f9 lunga della dimensione della parola di memoria della macchina, l’ algoritmo Shift Or<\/a> \u00e8 un algoritmo efficiente per risolvere il problema esatto di corrispondenza delle stringhe e si adatta facilmente a un’ampia gamma di problemi di corrispondenza approssimativa delle stringhe.<\/p>\n\n\n\n

Il primo algoritmo di corrispondenza delle stringhe in tempo lineare \u00e8 di Morris e Pratt<\/a> . \u00c8 stato migliorato da Knuth, Morris e Pratt<\/a> . La ricerca si comporta come un processo di riconoscimento da parte dell’automa, e un carattere del testo viene confrontato con un carattere del pattern non pi\u00f9 di log <\/sub>( m<\/em> +1) ( \"Phi\"\u00e8 il rapporto aureo \"rapporto). Hancart ha dimostrato che questo ritardo di un algoritmo correlato scoperto da Simon non fa pi\u00f9 di 1+log 2 <\/sub>m<\/em> confronti per carattere di testo. Questi tre algoritmi eseguono al massimo 2 n<\/em> -1 confronti di caratteri di testo nel caso peggiore.<\/p>\n\n\n\n

La ricerca con un automa finito deterministico<\/a> esegue esattamente n<\/em> ispezioni di caratteri di testo ma richiede uno spazio extra in O( m<\/em>\"sigma\" ). L’ algoritmo Forward Dawg Matching<\/a> esegue esattamente lo stesso numero di ispezioni dei caratteri di testo utilizzando l’automa suffisso del modello.<\/p>\n\n\n\n

L’ algoritmo Apostolico-Crochemore<\/a> \u00e8 un semplice algoritmo che esegue \"3\/2\"n<\/em> confronti di caratteri di testo nel caso peggiore.<\/p>\n\n\n\n

L’ algoritmo Not So Naive<\/a> \u00e8 un algoritmo<\/a> molto semplice con una complessit\u00e0 temporale quadratica nel caso peggiore, ma richiede una fase di pre-elaborazione in tempo e spazio costanti ed \u00e8 leggermente sublineare nel caso medio.Da destra a sinistra<\/a><\/p>\n\n\n\n

L’ algoritmo di Boyer-Moore<\/a> \u00e8 considerato l’algoritmo di corrispondenza delle stringhe pi\u00f9 efficiente nelle applicazioni usuali. Una sua versione semplificata (o l’intero algoritmo) \u00e8 spesso implementata negli editor di testo per i comandi “cerca” e “sostituisci”. Cole ha dimostrato che il numero massimo di confronti di caratteri \u00e8 strettamente limitato da 3 n<\/em> dopo la preelaborazione per modelli non periodici. Ha un tempo quadratico nel caso peggiore per i modelli periodici.<\/p>\n\n\n\n

Diverse varianti dell’algoritmo di Boyer-Moore evitano il suo comportamento quadratico. Le soluzioni pi\u00f9 efficienti in termini di numero di confronti di simboli sono state progettate da Apostolico e Giancarlo<\/a> , Crochemore et alii ( Turbo BM<\/a> ) e Colussi ( Reverse Colussi<\/a> ).<\/p>\n\n\n\n

I risultati empirici mostrano che le variazioni dell’algoritmo di Boyer e Moore progettato da Sunday ( Quick Search<\/a> ) e un algoritmo basato sull’automa suffisso di Crochemore et alii ( Reverse Factor<\/a> e Turbo Reverse Factor<\/a> ) sono le pi\u00f9 efficienti nella pratica.<\/p>\n\n\n\n

Gli algoritmi Zhu e Takaoka<\/a> e Berry-Ravindran<\/a> sono varianti dell’algoritmo Boyer-Moore che richiedono uno spazio extra in O<\/strong><\/em> ( \"sigma\"2<\/sup> ).In un ordine specifico<\/a><\/p>\n\n\n\n

I due primi algoritmi di corrispondenza delle stringhe nello spazio ottimale lineare sono dovuti a Galil-Seiferas<\/a> e Crochemore-Perrin ( algoritmo a due vie<\/a> ). Dividono il pattern in due parti, prima cercano la parte destra del pattern da sinistra a destra e poi, se non si verifica alcuna discrepanza, cercano la parte sinistra.<\/p>\n\n\n\n

Gli algoritmi di Colussi<\/a> e Galil-Giancarlo<\/a> suddividono l’insieme delle posizioni del pattern in due sottoinsiemi. Prima cercano i caratteri del modello le cui posizioni sono nel primo sottoinsieme da sinistra a destra e poi, se non si verifica una mancata corrispondenza, cercano i caratteri rimanenti da sinistra a destra. L’algoritmo Colussi \u00e8 un miglioramento rispetto all’algoritmo Knuth-Morris-Pratt ed esegue al massimo \"3\/2\"n<\/em> confronti di caratteri di testo nel caso peggiore. L’algoritmo Galil-Giancarlo migliora l’algoritmo Colussi in un caso speciale che gli consente di eseguire al massimo \"4\/3\"n<\/em> confronti di caratteri di testo nel caso peggiore.<\/p>\n\n\n\n

Gli algoritmi di Sunday’s Optimal Mismatch<\/a> e Maximal Shift<\/a> ordinano le posizioni del modello rispettivamente in base alla frequenza dei caratteri e allo spostamento iniziale.<\/p>\n\n\n\n

Gli<\/a> algoritmi Skip Search<\/a> , KMP Skip Search<\/a> e Alpha Skip Search<\/a> di Charras ( et alii<\/em> ) utilizzano i bucket per determinare le posizioni iniziali sul modello nel testo.In qualsiasi ordine<\/a><\/p>\n\n\n\n

L’ algoritmo di Horspool<\/a> \u00e8 una variante dell’algoritmo di Boyer-Moore<\/a> , utilizza una delle sue funzioni shift e l’ordine in cui vengono eseguiti i confronti dei caratteri del testo \u00e8 irrilevante. Questo vale anche per tutte le altre varianti come la Quick Search<\/a> di Sunday, Tuned Boyer-Moore<\/a> di Hume e Sunday, l’ algoritmo di Smith<\/a> e l’ algoritmo di Raita<\/a> .Definizioni<\/a><\/p>\n\n\n\n

Prenderemo in considerazione ricerche pratiche. Assumeremo che l’alfabeto sia l’insieme dei codici ASCII o un suo sottoinsieme. Gli algoritmi sono presentati in linguaggio di programmazione C, quindi per una parola w<\/em> di lunghezza \"ell\"i caratteri sono w<\/em> [0], … , w<\/em> [ \"ell\"-1] e w<\/em> [ \"ell\"] contenevano il carattere di fine speciale (carattere nullo) che non pu\u00f2 verificarsi da nessuna parte all’interno di ogni parola ma alla fine. Entrambe le parole, il motivo e il testo risiedono nella memoria principale.<\/p>\n\n\n\n

Introduciamo alcune definizioni.<\/p>\n\n\n\n

Una parola u<\/em> \u00e8 un prefisso<\/em> di una parola w<\/em> se esiste una parola v<\/em> (possibilmente vuota) tale che w<\/em> = uv<\/em> .<\/p>\n\n\n\n

Una parola v<\/em> \u00e8 un suffisso<\/em> di una parola w<\/em> se esiste una parola u<\/em> (possibilmente vuota) tale che w<\/em> = uv<\/em> .<\/p>\n\n\n\n

Una parola z<\/em> \u00e8 una sottostringa<\/em> o una sottoparola<\/em> o un fattore<\/em> di una parola w<\/em> se esistono due parole u<\/em> e v<\/em> (possibilmente vuote) tali che w<\/em> = uzv<\/em> .<\/p>\n\n\n\n

Un intero p<\/em> \u00e8 un periodo<\/em> di una parola w<\/em> if for i<\/em> , 0   \"leq\" i<\/em> < m<\/em> – p<\/em> , w<\/em> [ i<\/em> ]= w<\/em> [ i<\/em> + p<\/em> ]. Il periodo pi\u00f9 piccolo di w<\/em> \u00e8 chiamato periodo<\/em> , \u00e8 indicato con per<\/em> ( w<\/em> ).<\/p>\n\n\n\n

Una parola w<\/em> di lunghezza \"ell\"\u00e8 periodica<\/em> se la lunghezza del suo periodo pi\u00f9 piccolo \u00e8 minore o uguale a \"ell\"\/2, altrimenti \u00e8 non periodica<\/em> .<\/p>\n\n\n\n

Una parola w<\/em> \u00e8 fondamentale<\/em> se non pu\u00f2 essere scritta come una potenza di un’altra parola: non esistono n\u00e9 una parola z<\/em> n\u00e9 un intero k<\/em> tale che w<\/em> = z k<\/sup><\/em> .<\/p>\n\n\n\n

Una parola z<\/em> \u00e8 un bordo<\/em> di una parola w<\/em> se esistono due parole u<\/em> e v<\/em> tali che w<\/em> = uz<\/em> = zv<\/em> , z<\/em> \u00e8 sia un prefisso che un suffisso di w<\/em> . Nota che in questo caso | u<\/em> |=| v<\/em> | \u00e8 un periodo di w<\/em> .<\/p>\n\n\n\n

Il rovescio di una parola w<\/em> di lunghezza \"ell\"indicata con w R<\/sup><\/em> \u00e8 l’immagine speculare di w<\/em> ; w R<\/sup><\/em> = w<\/em> [ \"ell\"-1] w<\/em> [ \"ell\"-2] … w<\/em> [1] w<\/em> [0].
Un Automa Finito Deterministico (DFA) A \u00e8 un quadruplo ( Q<\/strong><\/em> , q 0<\/sub> , T<\/strong><\/em> , E<\/strong><\/em> ) dove:<\/p>\n\n\n\n

\"\" <\/td>Q<\/strong><\/em> \u00e8 un insieme finito di stati;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\"\" <\/td>q 0<\/sub> in Q<\/strong><\/em> \u00e8 lo stato iniziale;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\"\" <\/td>T<\/strong><\/em> , sottoinsieme di Q<\/strong><\/em> , \u00e8 l’insieme degli stati terminali;<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\"\" <\/td>E,<\/strong><\/em> sottoinsieme di ( Q<\/strong><\/em> .\"Sigma\". Q<\/strong><\/em> ), \u00e8 l’insieme delle transizioni.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

La lingua L<\/strong><\/em> ( A ) definita da A \u00e8 il seguente insieme:
\"\"<\/p>\n\n\n\n

Per ogni algoritmo esatto di string-matching presentato nel presente libro diamo prima le sue caratteristiche principali, poi abbiamo spiegato come funziona prima di dare il suo codice C. Successivamente mostriamo il suo comportamento su un tipico esempio dove x<\/em> =GCAGAGAG ey<\/em> =GCATCGCAGAGAGTATACAGTACG. Infine diamo un elenco di riferimenti dove il lettore trover\u00e0 presentazioni e dimostrazioni pi\u00f9 dettagliate dell’algoritmo. Ad ogni tentativo, le corrispondenze vengono materializzate in grigio chiaro mentre le discrepanze vengono mostrate in grigio scuro. Un numero indica l’ordine in cui vengono eseguiti i confronti dei caratteri, ad eccezione degli algoritmi che utilizzano gli automi, dove il numero rappresenta lo stato raggiunto dopo l’ispezione dei caratteri.Implementazione<\/a><\/p>\n\n\n\n

In questo libro, usiamo stringhe C e assumiamo che una stringa di lunghezza m<\/em> contenga un simbolo ( m<\/em> +1)-esimo (di solito assegnato con il valore ‘\\0’). In caso contrario, alcune implementazioni di algoritmi potrebbero andare in crash quando si accede a una posizione appena oltre l’effettivo ultimo carattere di una stringa. (Grazie a David B. Trout di Software Development Laboratories per aver indicato questo punto particolare).<\/p>\n\n\n\n

In questo libro useremo strumenti classici. Uno di questi \u00e8 un elenco collegato di numeri interi. Sar\u00e0 definito in C come segue:<\/p>\n\n\n\n

  struct _cell{ \n    int elemento; \n    struct _cell *next; \n  }; \n \n  typedef struct _cell *Lista;\n<\/pre>\n\n\n\n
Altre strutture importanti sono gli automi e in particolare gli automi suffissi (vedi capitolo 22<\/a> ). Fondamentalmente gli automi sono grafi diretti. Useremo la seguente interfaccia per manipolare gli automi:<\/p>\n\n\n\n
  Grafico newGraph(int v, int e); \n  Grafico newAutomaton(int v, int e); \n  Grafico newSuffixAutomaton(int v, int e); \n  int newVertex(Grafico g); \n  int getInitial(Grafico g); \n  isTerminal booleano(Grafico g, int v); \n  void setTerminal(Grafico g, int v); \n  int getTarget(Graph g, int v, unsigned char c); \n  void setTarget(Graph g, int v, unsigned char c, int t); \n  int getSuffixLink(Grafico g, int v); \n  void setSuffixLink(Graph g, int v, int s); \n  int getLength(Grafico g, int v); \n  void setLength(Graph g, int v, int ell); \n  int getPosition(Grafico g, int v); \n  void setPosition(Grafico g, int v, int p);\n  int getShift(Graph g, int v, unsigned char c);\n  void setShift(Graph g, int v, unsigned char c, int s); \n  void copyVertex(Graph g, int target, int source);\n<\/pre>\n\n\n\n
Segue una possibile implementazione di questa interfaccia.<\/p>\n\n\n\n
  struct _graph { \n    int vertexNumber, \n        edgeNumber, \n        vertexCounter, \n        initial, \n        *terminal, \n        *target, \n        *suffixLink, \n        *length, \n        *position, \n        *shift; \n  }; \n  \n  typedef struct _graph *Graph; \n  typedef int booleano; \n   \n#define UNDEFINED -1 \n  \n\/* restituisce una nuova struttura dati per \n   un grafo con v vertici ed e \narchi *\/ Graph newGraph(int v, int e) { \n   Graph g; \n\n   g = (Graph)calloc(1, sizeof(struct _graph)); \n   if (g == NULL) \n      error(\"newGraph\"); \n   g->numero vertice = v;\n   g->edgeNumber = e; \n   g->iniziale = 0; \n   g->vertexCounter = 1; \n   ritorno(g); \n} \n\n\n\/* restituisce una nuova struttura dati per \n   un automa con v vertici ed e bordi *\/ \nGraph newAutomaton(int v, int e) { \n   Graph aut; \n\n   aut = newGraph(v, e); \n   aut->target = (int *)calloc(e, sizeof(int)); \n   if (aut->target == NULL) \n      error(\"newAutomaton\"); \n   aut->terminal = (int *)calloc(v, sizeof(int)); \n   if (aut->terminal == NULL) \n      error(\"newAutomaton\"); \n   ritorno(auto); \n} \n\n\n\/* restituisce una nuova struttura dati per \n   un automa suffisso con v vertici ed e bordi *\/\nGraph newSuffixAutomaton(int v, int e) { \n   Graph aut; \n\n   aut = nuovoAutoma(v,e);\n   memset(aut->target, UNDEFINED, e*sizeof(int)); \n   aut->suffixLink = (int *)calloc(v, sizeof(int)); \n   if (aut->suffixLink == NULL) \n      error(\"newSuffixAutomaton\"); \n   aut->lunghezza = (int *)calloc(v, sizeof(int)); \n   if (aut->length == NULL) \n      error(\"newSuffixAutomaton\"); \n   aut->posizione = (int *)calloc(v, sizeof(int)); \n   if (aut->position == NULL) \n      error(\"newSuffixAutomaton\"); \n   aut->shift = (int *)calloc(e, sizeof(int)); \n   if (aut->shift == NULL) \n      error(\"newSuffixAutomaton\"); \n   ritorno(auto);\n \n  \n   un trie con v vertici ed e bordi *\/ \nGraph newTrie(int v,\n  \n   aut = newAutomaton(v, e); \n   memset(aut->target, UNDEFINED, e*sizeof(int)); \n   aut->suffixLink = (int *)calloc(v, sizeof(int)); \n   if (aut->suffixLink == NULL) \n      errore(\"newTrie\"); \n   aut->lunghezza = (int *)calloc(v, sizeof(int)); \n   if (aut->length == NULL) \n      error(\"newTrie\"); \n   aut->posizione = (int *)calloc(v, sizeof(int)); \n   if (aut->position == NULL) \n      error(\"newTrie\"); \n   aut->shift = (int *)calloc(e, sizeof(int)); \n   if (aut->shift == NULL) \n      error(\"newTrie\"); \n   ritorno(auto);\n\n \n   if (g != NULL && g->\n      return(g->vertexCounter++); \n   errore(\"nuovo vertice\"); \n} \n\n\n\/* restituisce il vertice iniziale del grafo g *\/ \nint getInitial(Graph g) { \n   if (g != NULL) \n      return(g->initial); \n   errore(\"getInitial\"); \n} \n\n\n\/* restituisce true se il vertice v \u00e8 terminale nel grafico g *\/ \nbooleano isTerminal(Graph g, int v) { \n   if (g != NULL && g->terminal != NULL && \n       v < g->vertexNumber) \n      return(g -> terminale[v]); \n   error(\"isTerminal\"); \n} \n\n\n\/* imposta il vertice v come terminale nel grafico g *\/ \nvoid setTerminal(Graph g, int v) { \n       v < g->vertexNumber) \n      g->terminal[v] = 1;\n      error(\"isTerminal\"); \n} \n\n\n\/* restituisce il target del bordo dal vertice v \n   etichettato dal carattere c nel grafico g *\/ \nint getTarget(Graph g, int v, unsigned char c) { \n   if (g != NULL && g->target != NULL && \n       v < g->NumeroVertice && v*c < g->NumeroEdge) \n      return(g->target[v*(g->NumeroEdge\/g->NumeroVertice) + \n                       c]); \n   errore(\"getTarget\"); \n} \n\n\n\/* aggiunge il bordo dal vertice v al vertice t \n   etichettato dal carattere c nel grafico g *\/ \nvoid setTarget(Graph g, int v, unsigned char c, int t) { \n   if (g != NULL && g->target ! = NULL &&\n       v*c <= g->edgeNumber && t < g->vertexNumber) \n      g->target[v*(g->edgeNumber\/g->vertexNumber) + c] = t; \n   else \n      errore(\"setTarget\"); \n} \n\n\n\/* restituisce il collegamento suffisso del vertice v nel grafico g *\/ \nint getSuffixLink(Graph g, int v) { \n   if (g != NULL && g->suffixLink != NULL && \n       v < g->vertexNumber) \n      return(g ->suffissoLink[v]); \n   error(\"getSuffixLink\"); \n} \n\n\n\/* imposta il collegamento del suffisso del vertice v \n   al vertice s nel grafico g *\/ \nvoid setSuffixLink(Graph g, int v, int s) { \n   if (g != NULL && g->suffixLink != NULL && \n       v < g- >Numero vertice && \n      s < g->vertexNumber) g->suffixLink[v] = s; \n   altro\n      error(\"setSuffixLink\"); \n}\n\n\n\/* restituisce la lunghezza del vertice v nel grafico g *\/ \nint getLength(Graph g, int v) { \n   if (g != NULL && g->length != NULL && \n       v < g->vertexNumber) \n      return(g-> lunghezza[v]); \n   errore(\"getLength\"); \n} \n\n\n\/* imposta la lunghezza del vertice v \nsull'intero ell nel grafico g *\/ void setLength(Graph g, int v, int ell) { \n   if (g != NULL && g->length != NULL && \n       v < g-> vertexNumber) \n      g->lunghezza[v] = ell; \n   else \n      errore(\"setLength\"); \n} \n\n\n\/* restituisce la posizione del vertice v nel grafico g *\/ \nint getPosition(Graph g, int v) { \n       v < g->\n   errore(\"getPosition\"); \n} \n\n\n\/* imposta la lunghezza del vertice v all'intero ell nel grafico g *\/ \nvoid setPosition(Graph g, int v, int p) { \n   if (g != NULL && g->position != NULL && \n       v < g-> vertexNumber) \n      g->posizione[v] = p; \n   else \n      errore(\"setPosition\"); \n} \n\n\n\/* restituisce lo spostamento del bordo dal vertice v \n   etichettato dal carattere c nel grafico g *\/ \nint getShift(Graph g, int v, unsigned char c) { \n   if (g != NULL && g->shift != NULL && \n       v < g->NumeroVertice && v*c < g->NumeroEdge) \n      return(g->shift[v*(g->NumeroEdge\/g->Numerovertice) +\n   errore(\"getShift\"); \n} \n\n\n\/* imposta lo spostamento del bordo dal vertice v \n   etichettato dal carattere c all'intero s nel grafico g *\/ \nvoid setShift(Graph g, int v, unsigned char c, int s) { \n   if (g != NULL && g- >shift != NULL && \n       v < g->vertexNumber && v*c <= g->edgeNumber) \n      g->shift[v*(g->edgeNumber\/g->vertexNumber) + c] = s; \n   else \n      errore(\"setShift\"); \n} \n\n\n\/* copia tutte le caratteristiche della sorgente del \n   vertice nella destinazione del vertice nel grafico g *\/ \nvoid copyVertex(Graph g, int target, int source) { \n   if (g != NULL && target < g->vertexNumber && \n       source < g-> \n         memcpy(g->\n                g->target + \n                source*(g->edgeNumber\/g->vertexNumber), \n                (g->edgeNumber\/g->vertexNumber)* \n                sizeof(int)); \n      if (g->shift != NULL) \n         memcpy(g->shift + \n                target*(g->edgeNumber\/g->vertexNumber), \n                g->shift + \n                source*(g->edgeNumber\/g->vertexNumber), \n                g->edgeNumber\/g->vertexNumber)* \n                sizeof(int)); \n      if (g->terminal != NULL) \n         g->terminal[target] = g->terminal[source]; \n      if (g->suffixLink != NULL) \n         g->length[target] = g-> \n         g->suffixLink[target] = g->\n      if (g->lunghezza != NULL) \n      if (g->posizione != NULL) \n         g->posizione[destinazione] = g->posizione[sorgente]; \n   } \n   else \n      errore(\"copyVertex\"); \n}<\/pre>\n\n\n\n
e-mails: {Christian.Charras<\/a>, Thierry.Lecroq<\/a>} @laposte.net
Tue Jan 14 15:03:31 MET 1997<\/small><\/em><\/p>\n","protected":false},"excerpt":{"rendered":"
introduzione La corrispondenza delle stringhe \u00e8 un argomento molto importante nel pi\u00f9 ampio dominio dell’elaborazione del testo. Gli algoritmi di corrispondenza delle stringhe sono componenti di base utilizzati nelle implementazioni di software pratici esistenti nella maggior…<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1421","page","type-page","status-publish"],"yoast_head":"\nintroduzione - Coupontoaster Blog<\/title>\n<meta name=\"description\" content=\"introduzione La corrispondenza delle stringhe \u00e8 un argomento molto importante nel pi\u00f9 ampio dominio dell'elaborazione del testo. Gli algoritmi di\" \/>\n<meta name=\"robots\" content=\"noindex, nofollow\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"introduzione - Coupontoaster Blog\" \/>\n<meta property=\"og:description\" content=\"introduzione La corrispondenza delle stringhe \u00e8 un argomento molto importante nel pi\u00f9 ampio dominio dell'elaborazione del testo. Gli algoritmi di\" \/>\n<meta property=\"og:url\" content=\"https:\/\/coupontoaster.com\/blog\/introduzione\/\" \/>\n<meta property=\"og:site_name\" content=\"Coupontoaster Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/coupontoaster\/\" \/>\n<meta property=\"article:modified_time\" content=\"2023-04-28T13:17:40+00:00\" \/>\n<meta property=\"og:image\" content=\"http:\/\/www-igm.univ-mlv.fr\/~lecroq\/string\/images\/gsigma.gif\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:site\" content=\"@coupontoaster\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"18 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/coupontoaster.com\/blog\/introduzione\/\",\"url\":\"https:\/\/coupontoaster.com\/blog\/introduzione\/\",\"name\":\"introduzione - Coupontoaster Blog\",\"isPartOf\":{\"@id\":\"https:\/\/coupontoaster.com\/blog\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/coupontoaster.com\/blog\/introduzione\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/coupontoaster.com\/blog\/introduzione\/#primaryimage\"},\"thumbnailUrl\":\"http:\/\/www-igm.univ-mlv.fr\/~lecroq\/string\/images\/gsigma.gif\",\"datePublished\":\"2021-08-25T10:34:49+00:00\",\"dateModified\":\"2023-04-28T13:17:40+00:00\",\"description\":\"introduzione La corrispondenza delle stringhe \u00e8 un argomento molto importante nel pi\u00f9 ampio dominio dell'elaborazione del testo. Gli algoritmi di\",\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/coupontoaster.com\/blog\/introduzione\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/coupontoaster.com\/blog\/introduzione\/#primaryimage\",\"url\":\"http:\/\/www-igm.univ-mlv.fr\/~lecroq\/string\/images\/gsigma.gif\",\"contentUrl\":\"http:\/\/www-igm.univ-mlv.fr\/~lecroq\/string\/images\/gsigma.gif\"},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/coupontoaster.com\/blog\/#website\",\"url\":\"https:\/\/coupontoaster.com\/blog\/\",\"name\":\"Coupontoaster Blog\",\"description\":\"We Appreciate The Quality Content\",\"publisher\":{\"@id\":\"https:\/\/coupontoaster.com\/blog\/#organization\"},\"alternateName\":\"Coupontoaster\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/coupontoaster.com\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/coupontoaster.com\/blog\/#organization\",\"name\":\"Coupontoaster\",\"alternateName\":\"Coupontoaster.com\",\"url\":\"https:\/\/coupontoaster.com\/blog\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/coupontoaster.com\/blog\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/coupontoaster.com\/blog\/wp-content\/uploads\/2024\/01\/coupontoaster_logo.webp\",\"contentUrl\":\"https:\/\/coupontoaster.com\/blog\/wp-content\/uploads\/2024\/01\/coupontoaster_logo.webp\",\"width\":291,\"height\":62,\"caption\":\"Coupontoaster\"},\"image\":{\"@id\":\"https:\/\/coupontoaster.com\/blog\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/coupontoaster\/\",\"https:\/\/x.com\/coupontoaster\"]}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"introduzione - Coupontoaster Blog","description":"introduzione La corrispondenza delle stringhe \u00e8 un argomento molto importante nel pi\u00f9 ampio dominio dell'elaborazione del testo. Gli algoritmi di","robots":{"index":"noindex","follow":"nofollow"},"og_locale":"en_US","og_type":"article","og_title":"introduzione - Coupontoaster Blog","og_description":"introduzione La corrispondenza delle stringhe \u00e8 un argomento molto importante nel pi\u00f9 ampio dominio dell'elaborazione del testo. Gli algoritmi di","og_url":"https:\/\/coupontoaster.com\/blog\/introduzione\/","og_site_name":"Coupontoaster Blog","article_publisher":"https:\/\/www.facebook.com\/coupontoaster\/","article_modified_time":"2023-04-28T13:17:40+00:00","og_image":[{"url":"http:\/\/www-igm.univ-mlv.fr\/~lecroq\/string\/images\/gsigma.gif","type":"","width":"","height":""}],"twitter_card":"summary_large_image","twitter_site":"@coupontoaster","twitter_misc":{"Est. reading time":"18 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/coupontoaster.com\/blog\/introduzione\/","url":"https:\/\/coupontoaster.com\/blog\/introduzione\/","name":"introduzione - Coupontoaster Blog","isPartOf":{"@id":"https:\/\/coupontoaster.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/coupontoaster.com\/blog\/introduzione\/#primaryimage"},"image":{"@id":"https:\/\/coupontoaster.com\/blog\/introduzione\/#primaryimage"},"thumbnailUrl":"http:\/\/www-igm.univ-mlv.fr\/~lecroq\/string\/images\/gsigma.gif","datePublished":"2021-08-25T10:34:49+00:00","dateModified":"2023-04-28T13:17:40+00:00","description":"introduzione La corrispondenza delle stringhe \u00e8 un argomento molto importante nel pi\u00f9 ampio dominio dell'elaborazione del testo. Gli algoritmi di","inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/coupontoaster.com\/blog\/introduzione\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/coupontoaster.com\/blog\/introduzione\/#primaryimage","url":"http:\/\/www-igm.univ-mlv.fr\/~lecroq\/string\/images\/gsigma.gif","contentUrl":"http:\/\/www-igm.univ-mlv.fr\/~lecroq\/string\/images\/gsigma.gif"},{"@type":"WebSite","@id":"https:\/\/coupontoaster.com\/blog\/#website","url":"https:\/\/coupontoaster.com\/blog\/","name":"Coupontoaster Blog","description":"We Appreciate The Quality Content","publisher":{"@id":"https:\/\/coupontoaster.com\/blog\/#organization"},"alternateName":"Coupontoaster","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/coupontoaster.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/coupontoaster.com\/blog\/#organization","name":"Coupontoaster","alternateName":"Coupontoaster.com","url":"https:\/\/coupontoaster.com\/blog\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/coupontoaster.com\/blog\/#\/schema\/logo\/image\/","url":"https:\/\/coupontoaster.com\/blog\/wp-content\/uploads\/2024\/01\/coupontoaster_logo.webp","contentUrl":"https:\/\/coupontoaster.com\/blog\/wp-content\/uploads\/2024\/01\/coupontoaster_logo.webp","width":291,"height":62,"caption":"Coupontoaster"},"image":{"@id":"https:\/\/coupontoaster.com\/blog\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/coupontoaster\/","https:\/\/x.com\/coupontoaster"]}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/coupontoaster.com\/blog\/wp-json\/wp\/v2\/pages\/1421","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/coupontoaster.com\/blog\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/coupontoaster.com\/blog\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/coupontoaster.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/coupontoaster.com\/blog\/wp-json\/wp\/v2\/comments?post=1421"}],"version-history":[{"count":0,"href":"https:\/\/coupontoaster.com\/blog\/wp-json\/wp\/v2\/pages\/1421\/revisions"}],"wp:attachment":[{"href":"https:\/\/coupontoaster.com\/blog\/wp-json\/wp\/v2\/media?parent=1421"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}