Autor Tema: Implementar un Algoritmo para cadenas en el alfabeto binario

0 Usuarios y 1 Visitante están viendo este tema.

24 Enero, 2018, 07:50 pm
Leído 5525 veces

Antoniio

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 261
  • Karma: +0/-0
  • Sexo: Masculino
Hola, buenas. Ciertamente este es un ejercicio complicado , tenemos que implementar el algoritmo de Knuth-Morris-Pratt (KMP) pero para cadenas en el alfabeto binario. Esta es una explicación del algoritmo:

"Este algoritmo está basado en la construcción de un AFD. El algoritmo KMP es un algoritmo de búsqueda de subcadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí (sobre ella se precalcula una tabla de valores), para determinar donde podría darse la siguiente existencia, sin necesidad de analizar más de 1 vez los caracteres de la cadena donde se busca.
El algoritmo KMP, trata de localizar la posición de comienzo de una cadena, dentro de otra. Antes que nada con la cadena a localizar se precalcula una tabla de saltos (conocida como tabla de fallos) que después al examinar entre si las cadenas se utiliza para hacer saltos cuando se localiza un fallo"

Estoy comenzando a leer este artículo: https://users.dcc.uchile.cl/~bebustos/apuntes/cc30a/BusqTexto/#2 donde muestra el algoritmo pero para localizar búsqueda en texto, la idea es la misma pero dentro del alfabeto binario, tomando en cuenta esta página donde se muestra:
https://es.convertbinary.com/alfabeto/

No pido que se me resuelta el ejercicio, solo ocupo un impulso, la idea de cómo comenzar a realizarlo, tener ideas de cómo podría ser para poder trabajar en él, la verdad es que no he logrado comprender cómo resolverlo...espero alguien pueda tomarse el tiempo, gracias de antemano.

Un saludo !.



26 Enero, 2018, 01:30 pm
Respuesta #1

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Si tienes un texto en ASCII, lo lógico es decodificarlo primero, es decir, darle una interpretación a los bytes entrantes y después aplicar el algoritmo.
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

26 Enero, 2018, 08:09 pm
Respuesta #2

Antoniio

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 261
  • Karma: +0/-0
  • Sexo: Masculino
Si tienes un texto en ASCII, lo lógico es decodificarlo primero, es decir, darle una interpretación a los bytes entrantes y después aplicar el algoritmo.

Bueno, sigo trabajando en ello, cuando tenga algo vengo aquí con los datos, un saludo.