Sobre el número máximo de factores frecuentes distintos en una cadena de símbolos

Abstract

Las cadenas de sımbolos, como fuente de informacion, siempre han sido un recurso del que poder extraer conocimiento y, actualmente, el numero de aplicaciones y casos reales que las usan sigue creciendo, de forma que avances en este ambito repercutiran en multiples disciplinas. En esta comunicacion se estudia la complejidad del problema de descubrir factores (subcadenas) frecuentes en cadenas de sımbolos de longitud n, añadiendo la caracterıstica de que dicha busqueda pueda estar dirigida por un soporte (frecuencia) k mınimo que deben alcanzar dichos factores. Se analiza como afecta este resultado a algoritmos conocidos para este problema y se calcula de manera efectiva el numero maximo de factores k-frecuentes en una cadena. Se llega a demostrar que, aunque la complejidad en general es cuadratica en la longitud n de la cadena, si el soporte k es al menosraiz(n), la complejidad es lineal en n. Ese soporte es suficientemente interesante.