Uma borda de string é um prefixo próprio que também é sufixo. As bordas permitem que um buscador reaproveite o trabalho depois de uma divergência. Se uma borda candidata não puder ser estendida, tente a borda dessa borda em vez de comparar o texto de novo desde o início. A tabela da função de prefixos registra esses comprimentos de retrocesso.
As correspondências sobrepostas deixam a regra de retrocesso visível. Depois de encontrar aba dentro de ababa, o último a pode iniciar a próxima correspondência. Zerar o comprimento já correspondido perderia essa ocorrência. A construção de palíndromos usa a mesma tabela de bordas em uma string unida à sua inversa por um separador que não existe no alfabeto da entrada.
Nem todo problema de strings precisa dessa tabela. Expandir a partir dos centros é uma solução quadrática clara para a tarefa do trecho palíndromo limitado. A correspondência de expressões restritas usa, em vez disso, programação dinâmica com dois prefixos. Declare cada gramática com precisão: o asterisco dela repete o átomo anterior, ao contrário do asterisco curinga isolado da lista de exercícios mista.
Reutilize bordas de strings e estados de prefixos para buscas com sobreposição e correspondências com restrições.