El borde de una cadena es un prefijo propio que también es sufijo. Los bordes permiten que un buscador reutilice trabajo después de un fallo. Si un borde candidato no se puede ampliar, prueba el borde de ese borde en lugar de volver a comparar el texto desde el principio. La tabla de función de prefijos registra esas longitudes de retroceso.
Las coincidencias solapadas hacen visible la regla de retroceso. Después de encontrar aba dentro de ababa, la última a puede empezar la siguiente coincidencia. Volver a poner a cero la longitud coincidente perdería esa aparición. La construcción de palíndromos usa la misma tabla de bordes sobre una cadena unida a su inversa con un separador que no está en el alfabeto de la entrada.
No todos los problemas de cadenas necesitan esa tabla. Expandir alrededor de los centros es una solución cuadrática clara para el tramo palindrómico acotado. La coincidencia de expresiones restringidas usa en cambio programación dinámica con dos prefijos. Indica con precisión cada gramática: su asterisco repite el átomo anterior, a diferencia del asterisco comodín suelto de la serie de práctica mixta.
Reutiliza los bordes de cadenas y los estados de prefijos para búsquedas solapadas y coincidencias con restricciones.