Al hacer esto en C, las únicas incorporaciones que usaría normalmente serían strlen y strncmp (o sus equivalentes de caracteres anchos / UTF8).
Estos se codifican fácilmente a mano, y en el caso de strncmp , no lo usaría de todos modos si desea que su algoritmo funcione en cualquier nivel que no sea algo cercano a O (longitud (S1) * longitud (S2)).
Para obtener mejores resultados en términos de rendimiento, probará carácter por carácter, con pseudocódigo similar a
- ¿Es una buena idea modelar otras estructuras de datos después de STD :: Vector?
- Traté de hacer este problema: 1984 - Pesadilla de navegación, pero obtengo TLE. ¿Cómo puedo mejorar mi algoritmo? ¿Cuál es la explicación de esta tarea?
- Cómo resolver radicales anidados como [math] (a + \ sqrt b \,) ^ {1/3} [/ math]
- ¿Todos los NP-HARD que son decidibles también son NP-Complete?
- En el algoritmo de búsqueda A * deberíamos tener una lista abierta y otra cerrada. ¿Cómo los implementa utilizando tanto el hashmap como una cola prioritaria en Java?
S1 es el candidato de subcadena
S2 es la cadena en la que estamos tratando de encontrar S1
L1 <- longitud de S1
L2 <- longitud de S2
si L1> L2, devuelve falso (S1 es más largo que S2, por lo que no puede ser una subcadena)
si L1 == 0, devuelve verdadero (la cadena vacía siempre es una subcadena)
si L2 == 0, devuelve falso (una cadena no vacía nunca es una subcadena de vacío)
actual (S2) <- primera pos de S2
mientras cierto
hacer
si no hay más caracteres en S2
falso retorno
más si actual (S2) == primero (S1)
actual (S1) <- primera posición de S1
hacer
avance S2
avance S1
si no hay más caracteres en S1, devuelve verdadero (subcadena encontrada)
si no hay más caracteres en S2, devuelve falso (no hay subcadenas posibles)
mientras actual (S1) == actual (S2)
más
avance (S2)
terminara si
hecho
Esto podría implementarse fácilmente en C, y sería más eficiente si no se usa strncmp , ya que sería O (longitud (S1) + longitud (S2)) si se implementa usando comparaciones carácter por carácter.
