String matching with a dynamic pattern
| dc.creator | Bruno Maletta Monteiro | |
| dc.date.accessioned | 2025-03-20T15:13:33Z | |
| dc.date.accessioned | 2025-09-08T23:12:29Z | |
| dc.date.available | 2025-03-20T15:13:33Z | |
| dc.date.issued | 2024-12-04 | |
| dc.description.abstract | Neste trabalho, nós estudamos variações do problema Casamento de Padrões: dadas duas strings, um padrão P e um texto T, queremos computar quantas vezes o padrão ocorre no texto. Nossa contribuição é focada no caso de um padrão dinâmico, ou seja, queremos suportar adição e remoção de caracteres no padrão, e após cada operação computar quantas vezes ele ocorre no texto. Nós mostramos um algoritmo simples usando Suffix Arrays que usa tempo O(log |T|), depois de tempo O(|T|) de pré-processamento. Nós mostramos como estender nossa solução para suportar remoção, transposição (mover a substring para outra posição) e cópia (copiar a substring e colar em uma posição específica) de substrings, na mesma complexidade de tempo. Nossa solução ainda pode ser estendida para suportar um texto online (adicionar caracteres em uma ponta do texto), mantendo as mesmas complexidades amortizadas de tempo. Também fazemos uma análise do tempo de execução do algoritmo proposto contra um algoritmo ingênuo, para demonstrar sua viabilidade. Também é discutida uma generalização do suffix array para várias strings. | |
| dc.description.sponsorship | CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior | |
| dc.identifier.uri | https://hdl.handle.net/1843/80790 | |
| dc.language | eng | |
| dc.publisher | Universidade Federal de Minas Gerais | |
| dc.rights | Acesso Aberto | |
| dc.subject | Computação – Teses | |
| dc.subject | Algoritmos de computador – Teses | |
| dc.subject | Complexidade computacional – Teses | |
| dc.subject | Processamento de vetor (Computação) – Teses | |
| dc.subject | Reconhecimento de padrões – Teses | |
| dc.subject.other | strings | |
| dc.subject.other | Algorithms | |
| dc.subject.other | suffix array | |
| dc.subject.other | string matching | |
| dc.title | String matching with a dynamic pattern | |
| dc.title.alternative | Casamento de padrões dinâmicos | |
| dc.type | Dissertação de mestrado | |
| local.contributor.advisor1 | Vinicius Fernandes dos Santos | |
| local.contributor.advisor1Lattes | http://lattes.cnpq.br/6270626469557436 | |
| local.contributor.referee1 | Victor Campos | |
| local.contributor.referee1 | Felipe Alves da Louza | |
| local.creator.Lattes | http://lattes.cnpq.br/0082041478569822 | |
| local.description.resumo | In this work, we study variations of the String Matching Problem: given two strings, a pattern P and a text T, we want to find how many times the pattern occurs in the text. We focus our contributions on the case of a dynamic pattern, that is, we want to support character additions and deletions to the pattern, and after each operation compute how many times it occurs in the text. We show a simple algorithm using Suffix Arrays that achieves O(log |T|) update time, after O(|T|) preprocess time. We show how to extend our solution to support substring deletion, transposition (moving a substring to another position of the pattern), and copy (copying a substring and pasting it in a specific position), in the same time complexities. Our solution can also be extended to support an online text (adding characters to one end of the text), maintaining the same amortized bounds. We also do a running time analysis of the proposed algorithm versus a naive solution, to illustrate its feasibility. A generalization of the suffix array for several strings is also discussed. | |
| local.publisher.country | Brasil | |
| local.publisher.department | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO | |
| local.publisher.initials | UFMG | |
| local.publisher.program | Programa de Pós-Graduação em Ciência da Computação |