Problema con un vector que contiene a otro

Xustis

Mi problema a realizar es que dados dos vectores, indicar si los valores del primero aparecen en el segundo en el mismo orden y de forma consecutiva a partir de alguna posicion del segundo. En caso afirmativo, retornar la posició de la primera aparicion.

Después de muchos intentos he perdido toda concentración y ya no soy capaz ni a entender que estaba haciendo practicamente, añado como lo tengo actualmente y gracias por vuestra ayuda:

gAdrev

#1
Tienes un pequeño cacao sí. Te paso un pseudocódigo para ver si sacas el Java. Ibas bien.


PARA CADA índice de ve2 "i":
   offset = 0
   MIENTRAS QUE 
      offset sea un índice válido de ve1
   Y
      i + offset sea un índice válido de ve2
   Y
      ve1[offset] == ve2[i+offset]
   ENTONCES
      incrementar offset
      SI offset es la longitud de ve2, ENTONCES devolver la posición actual
// termina el bucle
devolver -1

Si no te sale te puedo pasar código en otro lenguaje. El tema es que te salga en Java.

EDIT: una cosa que muchas veces se pasa por alto al empezar es que el for puede tener varias expresiones, por ejemplo, puedes hacer varias inicializaciones a la izquierda, varias operaciones a la derecha. Ejemplo tonto:

for(int i=0, j=0; i < LIMITE_I && j < LIMITE_J; i++, j+=2) { ... }
2 respuestas
E

Pues yo no le veo el fallo. Lo que si que comprobaría que vE2 >= vE1, poque si no es así ya puedes devolver return -1. También en el primer bucle puedes hacerlo hasta vE2.length()-vE1.length(). No se como optimiza el código Java, pero por si acaso poniendo esa operación antes del for (y no dentro) te ahorras estar haciéndola a cada pasada. Ahh, y en el if del final creo que debería ser vE1.length()-1, el tamaño siempre es el último índice mas uno (ya que el primer índice es 0, si fura 1 estaría todo solucionado, por eso en algunos lenguajes el primer índice es 1). <-- Esto ya estaba bien =P

EDIT: Pensándolo mejor, último vE1.length()-1 lo puedes dejar igual pero debes inicializar int contador = 1; (porque en el primer if ya cuentas un elemento). También lo podrías poner dentro del primer if, antes o después del pos++; Aunque como ha dicho #2 puedes poner el pos++ dentro del segundo for, que queda mejor (y ya si usas j en lugar de aux_i lo clavas). En el segundo bucle, como condición puedes poner pos < vE1.length(), es mas claro.

1 1 respuesta
Xustis

#3 #2 Gracias por los comentarios, mañana lo miraré que he estado con otra tarea y ni si quiera entré por aquí (cuando uno se concentra picando código se pasa el tiempo volando xD). Espero solucionarlo y si no igual tengo que tirar de compañeros, pero igualmente me habeis enseñado cosas y optimizado el código ;)

B

No se qué criterio de eficiencia se te impone, pero puedes obtener el match lineal usando KMP o alguna variante, lo digo porque esa idea de código es cancerígenamente lenta, y con segun que tamaños lo vas a notar y mucho.

KMP
Boyer-Moore

Xustis

Vale ya me sale, era lo del contador, muchas gracias. En cuanto a lo de KMP creo que eso me supera xD (primero de carrera)

1 respuesta
B

#6 aaagh, vale! Pues entonces olvida lo que he puesto.

11 días después
boqueron

La vuelta atras es tu amiga en estos casos, si lo consigues implementar con recursividad el algoritmo tiene un coste mucho menor y el algoritmo en si es mas facil. Prueba a hacerlo con backtracking y ya veras que diferencia.

2 respuestas
gAdrev

#8 Está empezando, bastante tiene con atinar el algoritmo básico entre errores de sintaxis.

B

#8 No entiendo nada, que coste tiene el "backtracking" que dices? Y aparte, picar el mismo algoritmo de #1 pero de forma recursiva no evita que sea theta(|P|*|T|) el coste. De hecho a efectos prácticos sería peor por el overhead adicional de las llamadas recursivas.

Usuarios habituales