Dada la cadena s, encuentre la cadena t más corta, de modo que, t^m = s

Question

Dada la cadena s, encuentre la cadena t más corta, de modo que, t^m = s.

Ejemplos:

s="aabbb" => t="aabbb" 
s="abab" => t = "ab" 

¿Qué tan rápido puede hacerse?

Por supuesto ingenuamente, por cada m divide | s |, puedo probar si substring (s, 0, | s |/m)^m = s.

Uno puede encontrar la solución en O (d (| s |) n) vez, donde d (x) es el número de divisores de s. ¿Se puede hacer de manera más eficiente?

Answer 1

Este es el problema de calcular el período de una cadena. Knuth, Morris and Pratt's sequential string matching algorithm es un buen lugar para comenzar. Esto se encuentra en un documento titulado "Coincidencia rápida de patrones en cadenas" de 1977.

Si desea hacerse elegante con él, consulte el documento "Encontrar todos los períodos y palíndromes iniciales de una cadena en paralelo" por Breslauer y Galil en 1991. Desde su resumen:

un óptimo O (log log n) tiempo algoritmo CRCW-PRAM para el cálculo de todos los períodos de una cadena que se presenta. Los algoritmos paralelos previos calculan el período solo si es más corto que la mitad de la longitud de la cadena . Este algoritmo se puede utilizar para encontrar todos los palíndromos iniciales de una cadena en el mismo tiempo y límites del procesador. Ambos algoritmos son lo más rápido posible sobre un alfabeto general. Derivamos un límite inferior para encontrar palíndromos mediante una modificación de un inferior previamente conocido destinado a encontrar el período de una cadena [3]. Cuando los procesadores p son disponibles, los límites se convierten en \ Theta (d n p e + log log d1 + p = ne 2p).

Answer 2

una modificación de Boyer-Moore podría manejar esto de O (n), donde n es la longitud de s

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

Answer 3

Sí, puede hacerlo en O(|s|) tiempo.

Puede buscar una cadena "objetivo" de longitud n en una cadena "fuente" de longitud m en O(n+m) tiempo. Crea una solución basada en eso.

Deje que tanto la fuente como el destino sean s. Una restricción adicional es que 1 y cualquier posición en la fuente que no divide |s| no son posiciones de inicio válidas para la coincidencia. Por supuesto, la búsqueda per se siempre fallará. Pero si hay una coincidencia parcial y ha llegado al final de la cadena de sourse, entonces tiene una solución para el problema original.

Answer 4

me gusta mucho esta cosa llamada z-algoritmo: http://www.utdallas.edu/~besp/demo/John2010/z-algorithm.htm

Para cada posición se calcula la subcadena más larga a partir de ahí, es también un prefijo de toda la cadena. (en tiempo lineal por supuesto).

a a b c a a b x a a a z 
    1 0 0 3 1 0 0 2 2 1 0 

Dada esta "z-mesa", es fácil de encontrar todas las cadenas que se pueden exponenciada a todo el asunto. Simplemente verifique todas las posiciones si pos+z[pos] = n.

En nuestro caso:

a b a b 
    0 2 0 

Aquí pos = 2 le da 2+z[2] = 4 = n por lo tanto, la cadena más corta que puede utilizar es el de longitud 2.

Esto incluso le permitirá encontrar casos en que sólo un prefijo de los partidos de cuerda exponenciadas, como:

a b c a 
    0 0 1 

Aquí (abc)^2 se puede reducir a su original, cuerda. Pero, por supuesto, si no quieres partidos como este, solo revisa los divisores.