Ver Tema - Ejercicio: encontrar la subcadena más larga

elesar · 2011-12-19 21:30 @937

Hola, soy nuevo en Perl, y necesitaría saber si alguien me puede ayudar a resolver el siguiente ejercicio:

"Leer de un archivo ya existente una cadena muy larga de caracteres, encontrar la subcadena repetida más larga."

Ejemplo:

$cadena="12345ja12345jaxd12345jaxd1117";

la subcadena "12345jaxd" de $cadena es la más larga repetida.

No sé cómo hacer para recorrer la cadena carácter por carácter e ir viendo si se repite en algún lado. Si alguien me puede ayudar con esto se lo agradecería mucho.

Muchas gracias. Saludos

explorer · 2011-12-19 22:01 @959

Bienvenido a los foros de Perl en español, elesar.

Pues se trata de un ejercicio interesante...

Un poco de matemáticas... Si la longitud de la cadena es l, entonces la cadena más larga que se puede repetir es de longitud l/2, y además, comenzará siempre en la posición 0.

O sea, que tenemos que buscar cadenas de longitud creciente, desde 1 a l/2.

La búsqueda de cadenas repetidas es mejor hacerla con la función index(), indicando la posición de la siguiente búsqueda.

Las cadenas que más se repiten las puedes guardar en hash, pero el caso es que solo nos piden un máximo, así que con el viejo sistema de guardar en una variable las veces que aparece el máximo, y en otra, qué máximo es, lo tenemos hecho.

P.D. Por aquí no 'solemos' resolver trabajos de clase. Pero sí resolvemos dudas de Perl. Quizás alguien se anime y te da una solución, pero lo ideal es que muestres antes algo de código.

elesar · 2011-12-20 20:05 @878

Gracias, hice algo de código pero está muy incompleto y en la variable $subcadena me da 0.

Te adjunto acá el código que hice:

#!c:/perl/bin/perl.exe
open(CADENA,"C:/cadena.txt") || die "No se encuentra el archivo";
$linea=<CADENA>;
print $linea;
close(CADENA);
$subcadena="";
$aux="";
$e=-1;
@array=split("",$linea);
foreach $letra(@array){
$e++;
for($e;$i<@array.length;$i++){
$subcadena=$subcadena+$array[$e+1]; # acá intento cargar la siguiente letra del array a la subcadena, pero no lo hace, quiero cargarlo como si fuera agregar un carácter
if(length($subcadena) gt $aux ){ # acá falta preguntar o buscar si se repite la cadena
$aux=$subcadena;
}
}

}
print "\nLa subcadena repetida más larga es: $subcadena";

Si me pueden ayudar con esto, se los agradecería mucho, no conozco las funciones de Perl, lo agarré hace unos días nada más y no conozco el lenguaje. Desde ya, muchas gracias.

Lo tengo casi resuelto, pero no anda bien la parte del buscar si se repite, con algunos ejemplos de cadenas no lo hace bien.

#!c:/perl/bin/perl.exe
open(CADENA,"C:/cadena.txt") || die "No se encuentra el archivo";
$linea=<CADENA>;
print $linea;
close(CADENA);
$subcadena="";
$aux="";
$e=-1;
@array=split("",$linea);
foreach $letra(@array){

$e++;
$i=$e;
for($e;$e<@array.length;$e++){
$subcadena .= "$array[$e]";
if($linea =~ /($subcadena){2,}/)
{
$res=1;
}
else{

$res=0;
}
if($res==1 && length($subcadena) > length($aux)){

$aux=$subcadena;
}
}
$e=$i;
$subcadena="";
}
print "\n$aux";

explorer · 2011-12-21 18:00 @791

La idea es buena, pero hay una serie de cuestiones que no están bien resueltas...

.length no existe en Perl. Quítalo
La expresión regular que usas para buscar cadenas utiliza el cuantificador {2,}, con lo que estás indicando que la $subcadena se debe repetir, al menos dos veces, seguidas, y decías que el problema era encontrar las repeticiones a lo largo de la $linea.
Podrías evitar el intercambio de valores en las variables $e e $i, si cada una de ellas tiene una misión clara
gt es para comparaciones alfanuméricas. Necesitas usar '>' para hacer comparaciones numéricas

Esta es mi versión, basada en la tuya:

Syntax: [ Download ] [ Hide ]

Using perl Syntax Highlighting

#!/usr/bin/perl
use strict;
use warnings;
use diagnostics;
 
my $linea = '12345ja12345jaxd12345jaxd1117';
 
my $aux;
my $aux_n = 0;
my @array = split //, $linea;
 
for my $e (0 .. $#array) {                  # $e recorre los índices de todo el @array
    my $subcadena = "";
 
    for (my $i = $e; $i < @array; $i++) {   # recorremos el resto de letras de la línea
 
        $subcadena .= $array[$i];           # subcadena a buscar
 
#        print "[$subcadena]:";
        
        my $pos = $e - 1;                   # damos un paso atrás, ya que luego sumamos 1
        my $cnt = 0;                        # contador de apariciones
 
        while ($pos < @array) {                         # usamos index para buscar,
            $pos = index($linea, $subcadena, $pos+1);   # a partir de la posición $pos+1
            if ($pos != -1) {                           # la encontramos
                $cnt++;                                 # contamos una vez más
            }
            else {                                      # no encontramos más,
                last;                                   # terminamos
            }
        }
 
#        print "$cnt\n";
 
        # Valor más alto: si ha habido más de una repetición y
        # la longitud es mayor de la encontrada hasta ahora
        if ( $cnt > 1  and  length($subcadena) > length($aux) ) {
            $aux   = $subcadena;
            $aux_n = $cnt;
        }
    }
}
 
print "[$aux][$aux_n]\n";               # informamos de la cadena y veces que aparece
 
__END__
[12345jaxd1][2]
 

Esta es otra versión, usando expresiones regulares, pero menos eficiente

Syntax: [ Download ] [ Hide ]

Using perl Syntax Highlighting

#!/usr/bin/perl
use 5.010;
use strict;
use warnings;
use diagnostics;
 
my $linea = '12345ja12345jaxd12345jaxd1117';
#say $linea;
 
my $aux;
 
$linea =~ /
    (.+)                                        # buscamos una subcadena
    .*?                                         # que está separado por unas letras
    \1                                          # de una copia de sí misma (vamos, otra repetición)
    (?{                                         # entonces, ejecutamos
        if (length($1) > length($aux)) {        # si lo encontrado es mayor de lo que teníamos
            $aux = $1;                          #   lo guardamos
            #say "[$aux]";                      #   y pintamos (opcional)
        }
    })
    (*FAIL)                                     # repite la búsqueda por toda la cadena
    /x;
 
say $aux;                                       # pintamos la subcadena encontrada
 
__END__
12345jaxd

P.D. Como curiosidad, en la cadena de búsqueda, hay otra subcadena de la misma longitud que la encontrada antes: 2345jaxd1. Para encontrar ésta última, basta con cambiar los '>' por '>='.

elesar · 2011-12-21 20:39 @902

Hola, muchas gracias , me sirvió la ayuda.
Te dejo cómo quedó el programa andando

Syntax: [ Download ] [ Hide ]

Using perl Syntax Highlighting

#!c:/perl/bin/perl.exe
open( CADENA, "C:/cadena.txt" ) || die "No se encuentra el archivo";
$linea = <CADENA>;
print $linea;
close(CADENA);
$subcadena = "";
$aux       = "";
@array     = split( "", $linea );
for $e ( 0 .. $#array ) {
    $subcadena = "";
    for ( $i = $e; $i < @array . length; $i++ ) {
        $subcadena .= "$array[$i]";
        $posi = $e - 1;
        $cont = 0;
        while ( $posi < @array ) {
            $posi = index( $linea, $subcadena, $posi + 1 );
            if ( $posi != -1 ) {
                $cont++;
            }
            else {
                last;
            }
        }
        if ( ( $cont > 1 ) && ( length($subcadena) > length($aux) ) ) {
 
            $aux = $subcadena;
        }
 
    }
 
}
print "\n$aux";

Así anda

Muchas gracias.

explorer · 2011-12-21 21:33 @939

Cosas que debes corregir:

Si estás empezando con Perl, es muy aconsejable tener activados 'strict' y 'warnings', para que sea Perl quien te ayude a programar
El '||' en el open() no es aconsejable ponerlo, pues puede dar problemas en el futuro. Mejor usar 'or'
El 'length' de la línea 11 NO forma parte del lenguaje, así que se trata de un error. Perl no te ha avisado porque no tienes activos los 'warnings'. Ya te dije que lo quitaras
Las comillas de la línea 12, sobran
El montón de paréntesis que has puesto en la línea 24 es porque usas '&&' en lugar de 'and'. Compara con mi código

Esta es otra versión, un poco más optimizada

Syntax: [ Download ] [ Hide ]

Using perl Syntax Highlighting

#!/usr/bin/perl 
use 5.010;
use strict;
use warnings;
use diagnostics;
 
my $linea = '12345ja12345jaxd12345jaxd1117';
#my $linea = 'abcdefghijklmnopqrstuvwxyz088';            # caso extremo
 
my $l     = length $linea;
my $aux   = '';
 
for my $e (0 .. $l-2) {                                 # recorremos desde el principio hasta el penúltimo
 
    my $maxima = ($l - $e) / 2;                         # longitud de la repetición máxima que podemos encontrar
 
    for my $i (1 .. $maxima) {                          # recorremos el resto de letras de la línea
        my $subcadena = substr $linea, $e, $i;          # subcadena a buscar
 
        my $pos = index $linea, $subcadena, $e+$i;      # buscamos a partir del final de la propia subcadena
 
        # Hemos encontrado una subcadena que se repite, mayor, si
        # hemos encontrado (al menos) una repetición, y
        # su longitud es mayor que el de la encontrada antes
        if ( $pos != -1  and  $i > length $aux ) {
            $aux   = $subcadena;                        # la recordaremos
        }
    }
}
 
say $aux;                                               # informamos de la cadena que más se repite
 
__END__

elesar · 2011-12-23 15:49 @700

Ok, muchas gracias por la ayuda. Saludos.

Publicidad

Socializa