algorithm - ppt - bellman ford algoritmo

¿Encontrar el ciclo de repetición más corto en palabras?

Question

Estoy a punto de escribir una función que me devolvería un período más corto de un grupo de letras que eventualmente crearía la palabra dada.

Por ejemplo, la palabra abkebabkebabkeb es creada por la palabra abkeb repetida. Me gustaría saber cómo analizar de manera eficiente la palabra de entrada, para obtener el período más corto de caracteres que crean la palabra de entrada.

Answer 1

Solución Regex:

Paso 1: Separe cada carácter con un carácter delimitador que no forme parte de la cadena de entrada, incluido uno final (es decir, ~ ):

(.)
$1~

Ejemplo de entrada: "abkebabkebabkeb"
Ejemplo de salida: "a~b~k~e~b~a~b~k~e~b~a~b~k~e~b~"

Pruébalo en línea en Retina. ( NOTA: Retina es un lenguaje de programación basado en Regex, diseñado para realizar pruebas rápidas de expresiones regulares y poder competir con éxito en desafíos de código de golf ) .

Paso 2: Use la siguiente expresión regular para encontrar la subcadena de repetición más corta (donde ~ es nuestro carácter delimitador elegido):

^(([^~]+~)*?)/1*$
$1

Explicación:

^(([^~]+~)*?)/1*$
^ $ # Start and end, to match the entire input-string
([^~]+~) # Capture group 1: One or more non-''~'' followed by a ''~''
( *?) # Capture group 2: Repeated zero or more time optionally
/1* # Followed by the first capture group repeated zero or more times
$1 # Replace the entire input-string with the first capture group match

Ejemplo de entrada: "a~b~k~e~b~a~b~k~e~b~a~b~k~e~b~"
Ejemplo de salida: "a~b~k~e~b~"

Pruébalo en línea en Retina.

Paso 3: Remueve nuestro carácter delimitador nuevamente, para obtener el resultado deseado.

~
<empty>

Ejemplo de entrada: "a~b~k~e~b~"
Ejemplo de salida: "abkeb"

Pruébalo en línea en Retina.

Aquí una implementación de ejemplo en Java.

Answer 2

Aquí hay un algoritmo O (n) correcto. El primer bucle for es la parte de creación de tablas de KMP. Hay varias pruebas de que siempre se ejecuta en tiempo lineal.

Como esta pregunta tiene 4 respuestas anteriores, ninguna de las cuales es O (n) y correcta, probé esta solución para la corrección y el tiempo de ejecución.

def pattern(inputv):
if not inputv:
return inputv
nxt = [0]*len(inputv)
for i in range(1, len(nxt)):
k = nxt[i - 1]
while True:
if inputv[i] == inputv[k]:
nxt[i] = k + 1
break
elif k == 0:
nxt[i] = 0
break
else:
k = nxt[k - 1]
smallPieceLen = len(inputv) - nxt[-1]
if len(inputv) % smallPieceLen != 0:
return inputv
return inputv[0:smallPieceLen]

Answer 3

Creo que hay una solución recursiva muy elegante. Muchas de las soluciones propuestas resuelven la complejidad adicional donde la cadena termina con parte del patrón, como abcabca . Pero no creo que se pida eso.

Mi solución para la versión simple del problema en clojure:

 (defn find-shortest-repeating [pattern string]
(if (empty? (str/replace string pattern ""))
pattern
(find-shortest-repeating (str pattern (nth string (count pattern))) string)))
(find-shortest-repeating "" "abcabcabc") ;; "abc"

Pero tenga en cuenta que esto no encontrará patrones que no estén completos al final.

Answer 4

Encontré una solución basada en tu publicación, que podría tener un patrón incompleto:

(defn find-shortest-repeating [pattern string]
(if (or (empty? (clojure.string/split string (re-pattern pattern)))
(empty? (second (clojure.string/split string (re-pattern pattern)))))
pattern
(find-shortest-repeating (str pattern (nth string (count pattern))) string)))

Answer 5

Este es un ejemplo para PHP:

<?php
function getrepeatedstring($string) {
if (strlen($string)<2) return $string;
for($i = 1; $i<strlen($string); $i++) {
if (substr(str_repeat(substr($string, 0, $i),strlen($string)/$i+1), 0, strlen($string))==$string)
return substr($string, 0, $i);
}
return $string;
}
?>

Answer 6

Funciona en casos como bcbdbcbcbdbc.

function smallestRepeatingString(sequence){
var currentRepeat = '''';
var currentRepeatPos = 0;
for(var i=0, ii=sequence.length; i<ii; i++){
if(currentRepeat[currentRepeatPos] !== sequence[i]){
currentRepeatPos = 0;
// Add next character available to the repeat and reset i so we don''t miss any matches inbetween
currentRepeat = currentRepeat + sequence.slice(currentRepeat.length, currentRepeat.length+1);
i = currentRepeat.length-1;
}else{
currentRepeatPos++;
}
if(currentRepeatPos === currentRepeat.length){
currentRepeatPos = 0;
}
}
// If repeat wasn''t reset then we didn''t find a full repeat at the end.
if(currentRepeatPos !== 0){ return sequence; }
return currentRepeat;
}

Answer 7

Mi solución: la idea es encontrar una subcadena desde la posición cero para que sea igual a la subcadena adyacente de la misma longitud, cuando se encuentre dicha subcadena devuelva la subcadena. Tenga en cuenta que si no se encuentra una subcadena de repetición, estoy imprimiendo la cadena de entrada completa.

public static void repeatingSubstring(String input){
for(int i=0;i<input.length();i++){
if(i==input.length()-1){
System.out.println("There is no repetition "+input);
}
else if(input.length()%(i+1)==0){
int size = i+1;
if(input.substring(0, i+1).equals(input.substring(i+1, i+1+size))){
System.out.println("The subString which repeats itself is "+input.substring(0, i+1));
break;
}
}
}
}

Answer 8

O (n) solución. Supone que toda la cadena debe estar cubierta. La observación clave es que generamos el patrón y lo probamos, pero si encontramos algo en el camino que no coincide, debemos incluir toda la cadena que ya probamos, por lo que no debemos volver a observar esos caracteres.

def pattern(inputv):
pattern_end =0
for j in range(pattern_end+1,len(inputv)):
pattern_dex = j%(pattern_end+1)
if(inputv[pattern_dex] != inputv[j]):
pattern_end = j;
continue
if(j == len(inputv)-1):
print pattern_end
return inputv[0:pattern_end+1];
return inputv;

Answer 9

Respuesta súper retrasada, pero recibí la pregunta en una entrevista, aquí estaba mi respuesta (probablemente no sea la más óptima, pero también funciona para casos de prueba extraños).

private void run(String[] args) throws IOException {
File file = new File(args[0]);
BufferedReader buffer = new BufferedReader(new FileReader(file));
String line;
while ((line = buffer.readLine()) != null) {
ArrayList<String> subs = new ArrayList<>();
String t = line.trim();
String out = null;
for (int i = 0; i < t.length(); i++) {
if (t.substring(0, t.length() - (i + 1)).equals(t.substring(i + 1, t.length()))) {
subs.add(t.substring(0, t.length() - (i + 1)));
}
}
subs.add(0, t);
for (int j = subs.size() - 2; j >= 0; j--) {
String match = subs.get(j);
int mLength = match.length();
if (j != 0 && mLength <= t.length() / 2) {
if (t.substring(mLength, mLength * 2).equals(match)) {
out = match;
break;
}
} else {
out = match;
}
}
System.out.println(out);
}
}

Casos de prueba:

abcabcabcabc
bcbcbcbcbcbcbcbcbcbcbcbcbcbc
dddddddddddddddddddd
adcdefg
bcbdbcbcbdbc
Hola infierno

Código de devoluciones:

a B C
antes de Cristo
re
adcdefg
bcbdbc
Hola infierno

Answer 10

Se me ocurrió una solución simple que funciona perfectamente incluso con cuerdas muy grandes.
Implementación de PHP:

function get_srs($s){
$hash = md5( $s );
$i = 0; $p = '''';
do {
$p .= $s[$i++];
preg_match_all( "/{$p}/", $s, $m );
} while ( ! hash_equals( $hash, md5( implode( '''', $m[0] ) ) ) );
return $p;
}