En informática , un índice de subcadena es una estructura de datos que proporciona búsqueda de subcadena en un texto o colección de texto en tiempo sublineal . Si tiene un documento de longitud o un conjunto de documentos de longitud total , puede localizar todas las apariciones de un patrón en el tiempo. (Ver notación O grande ).
La frase índice de texto completo también se utiliza a menudo para un índice de todas las subcadenas de un texto. Pero esto es ambiguo, ya que también se utiliza para índices de palabras normales, como archivos invertidos y recuperación de documentos . Ver búsqueda de texto completo .
Los índices de subcadenas incluyen:
