Buscar cadenas cíclicas

Question

Estoy buscando la manera más eficiente de almacenar cadenas binarias en una estructura de datos (función de inserción) y luego al obtener una cadena, quiero verificar si hay alguna cadena cíclica de la cadena dada en mi estructura.

Pensé en almacenar las cadenas de entrada en un Trie pero luego cuando intenté determinar si alguna cadena cíclica de la cadena que obtuve ahora estaba insertada en el Trie significa hacer | s | busca en el Trie todas las cadenas cíclicas posibles.

¿Hay alguna manera de hacerlo de manera más eficiente mientras que la complejidad del lugar será como en un Trie?

Nota: Cuando digo cadenas cíclicas de una cadena quiero decir que, por ejemplo, todas las cadenas cíclicas de 1011 son: 0111, 1110, 1101, 1011

Answer 1

¿Se puede llegar a una función canonicalizing para las cadenas cíclicas en base a los siguientes:

1. Encuentra la mayor cantidad de ceros.
2. Gire la cadena para que esa ejecución de ceros esté en la parte delantera.
3. Para cada carrera de ceros de igual tamaño, vea si al girar hacia adelante produce una cadena lexicográficamente menor y, si es así, úselo.

Esto canonicalize todo en la clase de equivalencia (1011, 1101, 1110, 0111) a la lexicográfico menos valor: 0111.

0101010101 es una instancia espinosa para el que este algo no va a funcionar bien, pero si sus bits se distribuyen aleatoriamente, debería funcionar bien en la práctica para cadenas largas.

A continuación, puede utilizar hash basado en la forma canónica o utilizar un trie que incluirá solo la cadena vacía y las cadenas que comienzan con 0 y una sola ejecución trie responderá a su pregunta.

EDIT:

si tengo una cadena de una longitud | s | puede llevar mucho tiempo encontrar el valor menos lexicográfico. ¿Cuánto tiempo demorará realmente?

Es por eso que dije 010101.... es un valor por el que funciona mal. Digamos que la cadena es de longitud ny la más larga de 1 es de longitud r. Si los bits se distribuyen aleatoriamente, la duración de la ejecución más larga es O (log n) de acuerdo con "Distribution of longest run".

El tiempo para encontrar la carrera más larga es O (n). Puede implementar desplazamiento usando un desplazamiento en lugar de una copia de búfer, que debe ser O (1). El número de ejecuciones es el peor caso O (n/m).

Entonces, el tiempo para hacer el paso 3 debe ser

1. encontrar otras carreras largas: una O (n) Pase con O (log n) caso medio de almacenamiento, O (n) peor de los casos
2. Para cada ejecución: O (log n) promedio de casos, O (n) peor caso
3.   Cambie y compare lexicográficamente: O (log n) promedio de casos ya que la mayoría de las comparaciones de cadenas elegidas al azar fallan anticipadamente, O (n) el peor caso .

Esto lleva al peor caso de O (n²) pero un caso promedio de O (n + log² n) ≅ O (n).

Answer 2

Tiene n cadenas s1..sn y se le da una cadena t para saber si una permutación cíclica de t es una subcadena de cualquier s1..sn. Y desea almacenar las cadenas de la manera más eficiente posible. ¿Entendí tu pregunta correctamente?

Si es así, aquí hay una solución, pero con un gran tiempo de ejecución: para una entrada dada t, let t '= concat (t, t), verifique t' con cada s en s1..sn para ver si la subsecuencia más larga de t 'y sm es al menos | t | Si | si | = k, | t | = l se ejecuta en O (n.k.l) tiempo. Y puede almacenar s1..sn en cualquier estructura de datos que desee. ¿Eso es lo suficientemente bueno o tú?