Rappresentazioni compatte dell'automa suffisso per lo string matching

String matching is a fundamental problem in computer science, with a myriad of direct applications into several distinct areas of computing, including information retrieval, data compression, bioinformatics, natual language processing, linguistics and network security. It consists in finding all the occurrences of a pattern x of length m in a text y of length n, both drawn from a common alphabet Σ of size σ. The problem has attracted researchers’ interest over the years, inspiring solutions of particular practical and theoretical interest. Among them, those based on automata deserve a special mention, since they have always led to the design of flexible and efficient algorithms.

Quello dello string matching è un problema fondamentale nell'informatica, con una miriade di problemi di applicazioni dirette in diverse aree distinte dell’informatica, comprese i sistemi di gestione e compressione dei dati, la bioinformatica, l'elaborazione del linguaggio naturale, la linguistica e la sicurezza delle reti. Consiste nel trovare tutte le occorrenze di un pattern x di lunghezza m in un testo y di lunghezza n, entrambi tratti da un alfabeto comune Σ di dimensione σ. Il problema ha attirato negli anni l'interesse dei ricercatori, ispirando soluzioni di particolare interesse pratico e teorico. Tra questi, quelli basati sugli automi meritano una menzione speciale, poiché hanno sempre portato alla progettazione di strutture flessibili e algoritmi efficienti.