-2

tengo un proyecto en el cual tengo que buscar coincidencias de caracteres entre 3 diferentes Strings apartir de 4 caracteres por ejemplo:

String cadena1 = "aaattkggl"
String cadena2 = "rrattkmmt"
String cadena3 = "wwattkkllg"

como se puede observar entre las 3 cadenas se encuentran los caracteres "attk" y el programa deberia imprimir "attk".

en caso de tener mas de 4 caracteres unidos en las 3 cadenas deberia imprimirlos, ejemplo:

String cadena1 = "cadenaxyuiop"
String cadena2 = "qwertcadenaxqwert"
String cadena3 = "asdfghcadenax"

se deberia imprimir: "cadenax"

gracias a otro usuario pude avanzar con este codigo:

    //Pedir datos al usuario y validarlos
    System.out.print("Ingrese primer cadena: ");
    cadena1 = leer.nextLine();
    if (cadena1.contains("b")||cadena1.contains("j")||cadena1.contains("ñ")||cadena1.contains("x")||cadena1.contains("z"))
    {
        System.out.println("La cadena contiene caracteres invalidos");
    }
    else
    {
        System.out.println("\n");
        System.out.print("Ingrese segunda cadena: ");
        cadena2 = leer.nextLine();
        if (cadena2.contains("b")||cadena2.contains("j")||cadena2.contains("ñ")||cadena2.contains("x")||cadena2.contains("z"))
        {
            System.out.println("La cadena contiene caracteres invalidos");
        }
        else
        {
            System.out.println("\n");
            System.out.print("Ingrese tercer cadena: ");
            cadena3 = leer.nextLine();
            if (cadena3.contains("b")||cadena3.contains("j")||cadena3.contains("ñ")||cadena3.contains("x")||cadena3.contains("z"))
            {
                System.out.println("La cadena contiene caracteres invalidos");
            }

            //dividir la cadena en 4 caracteres y compararlos con las otras cadenas
            else 
            {
                System.out.println("\n***************************************************");
                for (int i=4; i<cadena1.length();i++)
                {
                    String[] partes = cadena1.split("(?<=\\G.{" + i + "})");
                    for (String parte : partes)
                    {
                        if (parte.length() < 4) break;
                        if(cadena2.contains(parte)&&cadena3.contains(parte))
                        cadenator.add(parte);
                    }
                }
            }

            System.out.println(cadenator);
        }
    }
}

pero no logro que pueda imprimir el resultado esperado con cualquier cadena, como la del primer ejemplo.

de igual manera deberia poder imprimir varias coincidencias en el caso de haberlas, ejemplo:

String cadena1 = "holaxxxxxxamigo"
String cadena2 = "amigottttttttthola"
String cadena3 = "ggggggggholagamigo"

esto deberia imprimir "hola" - "amigo"

Si alguien podria ayudarme, lo agradeceria muchisimo.

15
  • Si es una tarea para ingenería de sistemas, lo tienes permitido de usar expresiónes regulares? Podrías mostrar los esfuerzos de código que has hecho para solucionar el problema? Puedes tratar de especificar más preciso que es una "similtud" en tu contexto? (Por ejemplo cuantos caracteres en fila tienen que ser iguales para contar como similtud) Commented el 28 mar. 2017 a las 2:55
  • debe haber una similitud de 4 caracteres en las 3 cadenas por ejemplo: cadena1 = kkasjdkjdasHOLAasdasoijdasd cadena 2 = HOLAkdashdshowqeppopoip cadena 3 = xzvczvxcxzvczxbvzcxbHOLA en las 3 cadenas hay similitud de 4 caracteres juntos que forman la palabra HOLA, no se si me di a entender?
    – Erick Lugo
    Commented el 28 mar. 2017 a las 3:23
  • Mínimo y máximo 4 caracteres?
    – Dev. Joel
    Commented el 28 mar. 2017 a las 3:33
  • @Dev.Joel mínimo 4 caracteres, por ejemplo si tienes [HOLAAXXXXX] [KKKKKKKHOLAA] [YYYYHOLAAYYY] deberia imprimir: "HOLAA"
    – Erick Lugo
    Commented el 28 mar. 2017 a las 3:35
  • 1
    @Mariano intente eliminar una pregunta para evitar el duplicado pero al parecer no tengo permisos para realizar esa accion, voy a editar correctamente la primera para poder eliminar esta pregunta. Gracias y perdón.
    – Erick Lugo
    Commented el 31 mar. 2017 a las 4:34

5 respuestas 5

1

Básicamente lo que hace este código es separar la primera cadena en partes desde 4 caracteres hacia adelante haciendo uso de una expresión regular (?<=\\G.{" + numerodecaracteres+ "}) teniendo esas partes se hace uso del método contains de la clase String. sí dicha parte se encuentra en las otras dos cadenas se imprime.

String One, Two, Three;
System.out.print("Ingrese cadena de aminoacidos numero 1: ");
One= leer.nextLine();

System.out.print("Ingrese cadena de aminoacidos numero 2: ");
Two= leer.nextLine();

System.out.print("Ingrese cadena de aminoacidos numero 3: ");
Three= leer.nextLine();
List<String> repeats= new ArrayList<>();
for (int i = 0; i < One.length(); i++) { 
    for (int j = 4; j < One.length(); j++) {
        String[] parts = One.substring(i,One.length()).split("(?<=\\G.{" + j + "})");
        String part= parts[0];
        if(part.length()<4) break;
        if(Two.contains(part) && Three.contains(part)){
            if(!repeats.contains(part)) repeats.add(part);
        }
   }
}
1
  • Los comentarios no deben usarse para discusiones extendidas; esta conversación ha sido trasladada a un chat.
    – user227
    Commented el 8 abr. 2017 a las 18:57
1

Una alternativa asegurando coincidencias de maximo tamaño para n Strings

import java.util.ArrayList;
import java.util.Iterator;


public class StringFind {

    private String[] strings;

    public StringFind(String... strings){
        this.strings=strings;
    }

    private String match(String string){
        // buscar string en strings[1]-strings[length-1];
        int found = 1;
        for (int i = 1; i<strings.length; i++){
            if (strings[i].contains(string)) found++;
        }
        return (found == strings.length) ? string : null;
    }

    public ArrayList<String> getMatches(){
        ArrayList<String> list = new ArrayList<String>();
        String lastMatch="";
        // recorrer substrings desde 0
        for (int i = 0; i<strings[0].length()-4; i++){
            String resto = strings[0].substring(i);
            // buscar substring hasta minimo tamaño 4
            for (int j = resto.length(); j>3; j--){
                // buscar en otras cadenas
                String match = match(resto.substring(0, j));
                // ignorar si es parte del ultimo resultado agregado
                if (match!=null && !lastMatch.contains(match) ){
                    // recordar y agregar
                    lastMatch=match;
                    list.add(match);
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        StringFind sf = new StringFind("holaxxxxxxamigo", "amigottttttttthola", "ggggggggholagamigo");
        ArrayList<String> list = sf.getMatches();
        Iterator i = list.iterator();
        while(i.hasNext()){
            System.out.println(i.next());
        }

    }

}

Salida:

hola
amigo
1
  • lo pruebo y te comento, te agradezco por comentarlo.
    – Erick Lugo
    Commented el 31 mar. 2017 a las 4:49
1

El problema que quieres resolver se llama Longest common substring (LCS) (no confundir con Longest Common Subsequence). Un algoritmo para hacer esto luce como el siguiente:

(He modificado algunas partes para que muestre todas las coincidencias)

public class Main {

    public static void main(String[] args) {
        String s1 = "holaxperrxquetlssaxxxxamigos";
        String s2 = "amigottttquetlssatttttperrholas";

        System.out.println(allLongestCommonSubstring(s1, s2));
    }

    private static ArrayList allLongestCommonSubstring(String s1, String s2) {
        ArrayList<String> palabras = new ArrayList<>();

        ciclo:
        // recorrer caracter por caracter el string "s1"
        for (int i = 0, ilargo = s1.length(); i < ilargo; i++) {
            // para cada caracter de "s1" recorrer todos los de "s2"
            for (int j = 0, jlargo = s2.length(); j < jlargo; j++) {

                // contador de maximo
                int max = 0;

                // comparar "s1" frente a "s2" para encontrar la palabra
                while (s1.charAt(i + max) == s2.charAt(j + max)) {

                    // por cada coincidencia aumentar el maximo
                    max++;

                    // pero si el maximo excede el largo de algunos de los strings, romper el ciclo
                    if ((i + max >= ilargo) || (j + max >= jlargo)) {
                        break;
                    }
                }

                // si la cantidad de coincidencias es mayor que 3
                if (max > 3) {
                    // obtener la cadenas desde i hasta donde terminan de coincidir (i+max)
                    palabras.add(s1.substring(i, (i + max)));

                    if (i + max >= ilargo) {
                        // si está al final, saltar los caracteres que quedan y romper el ciclo
                        break ciclo;
                    } else {
                        // si no, saltar la palabra encontrada
                        i += (i + max < ilargo) ? max : 0;
                    }
                }
            }
        }

        return palabras;
    }
}

Puedes ver mas implementaciones en la Wiki.

3
  • Iba a responder en la otra pregunta, pero la cerraron :( Te recomiendo que le pongas el nombre de la otra a esta, ya que explica mejor lo que quieres hacer :P Commented el 31 mar. 2017 a las 5:01
  • Hola @arie CwHat muchas gracias por tu codigo comentado, ya edite las dos preguntas y trate de eliminar la segunda pero no puedo hacerlo porque ya tiene respuestas. tu codigo me resultó mas fácil de entender porque esta a mi nivel (estoy en segundo semestre en la uni) a comparación de lo que otros usuarios me han compartido que tuve que investigar sobre algunas partes. un saludo.
    – Erick Lugo
    Commented el 31 mar. 2017 a las 5:09
  • Como esta función devuelve un arrayList (un arreglo dinámico) puedes encontrar las coincidencias por pares : s1 - s2, s1 - s3. Luego intersectas los arreglos con una función como la que está en esta respuesta Commented el 31 mar. 2017 a las 5:21
1

Creo que esto te puede ayudar:

package cm;

public class Temp {
    public static void main(String[] args) {
        final String cadena1 = "cadenaxyuiop";
        final String cadena2 = "qwertcadenaxqwert";
        final String cadena3 = "asdfghcadenax";
        final String cadena4 = "cadenaxPorPaolo";

        final String[] cadenas = {cadena1, cadena2, cadena3, cadena4};
        String coincidencia = "";
        String coincidenciaFinal = "";

        for (int i = 1; i &lt; cadenas.length; i++) { // no es necesario comprobar la primera cadena

            if (!(coincidencia.length() > 0)) {
                final String cadena = cadenas[i];
                final String cadenaAnterior = cadenas[i - 1];

                for (int z = 0; z &lt; cadenaAnterior.length(); z++) { // se recorre la cadena anterior
                    final String caracterEvaluar = String.valueOf(cadenaAnterior.charAt(z));

                    // se hace la comprobacion de coincidencias
                    if (coincidencia.equals(cadena)) { 
                        if (cadena.contains(coincidencia)) {
                            coincidencia += caracterEvaluar;
                        }
                    } else {
                        if (cadena.contains(caracterEvaluar)) {
                            coincidenciaFinal += caracterEvaluar;
                            coincidencia = caracterEvaluar;
                        }
                    }
                }
            }
        }

        System.out.println("Coincidencia: " + coincidenciaFinal);
    }
}
6
  • Hola Paolo, lo acabo de testear y luce bien, déjame probar con otras cadenas y te comento el resultado final, gracias.
    – Erick Lugo
    Commented el 31 mar. 2017 a las 3:57
  • Recueda que debes meterle mano aún a este código.
    – Paolo
    Commented el 31 mar. 2017 a las 4:00
  • si lo se, creo que se puede notar mi inexperiencia pero es que apenas estoy aprendiendo en la universidad. si, todavía tengo que adaptarlo a lo que pidió mi maestro, pero lo que enviaste es la parte crucial de el programa.
    – Erick Lugo
    Commented el 31 mar. 2017 a las 4:02
  • Lo vivo ahora, ¡Aún nos queda mucho que aprender muchacho!
    – Paolo
    Commented el 31 mar. 2017 a las 4:03
  • Hola de nuevo Paolo, acabo de probar tu código con diferentes cadenas y pude notar que no imprime los resultados esperados. como por ejemplo con las cadenas: "aaattkggl" - "rrattkmmt" - "wwattkkllg" deberia imprimir: "attk" ya que como puedes observar en las 3 cadenas son los caracteres que se repiten.
    – Erick Lugo
    Commented el 31 mar. 2017 a las 4:13
0

llego con un par de años de retraso, me gustó el desafio, hay un problema con el planteamiento, se deben buscar las palabras más largas, por lo que en el caso de "hola amigo", solo se puede devolver "amigo hola", ya que si buscamos primero las más cortas, nos devolvería "hola amig migo amigo".

String buscarCoincidencias( String cadenaA, String cadenaB, String cadenaC, String resultado ) {
   int longTexto = cadenaA.length();
   for( int longPalabra = longTexto; longPalabra > 3; longPalabra-- ) {
      for( int k = 0; k <= longTexto - longPalabra; k++ ) {
         String subCadena = cadenaA.substring( k, k + longPalabra );
            System.out.println( subCadena );
         if( cotejar( subCadena, cadenaB ) && cotejar( subCadena, cadenaC ) ) {
            if( resultado.equals( "" )) {
               resultado = subCadena; 
            }
            else {
               resultado += ","+ subCadena;
            }
            cadenaA = cadenaA.replace( subCadena, "" );
            System.out.println( cadenaA );
            if( cadenaA.length() < 4 ) {
               return resultado;
            }
            return buscarCoincidencias( cadenaA, cadenaB, cadenaC, resultado );
         }
      }
   }
   return resultado;
}
  
boolean cotejar( String textoParaBuscar, String textoEnQueBuscar ) {
   int longTexto = textoEnQueBuscar.length();
   for( int longPalabra = longTexto; longPalabra > 3; longPalabra-- ) {
      for( int k = 0; k <= longTexto - longPalabra; k++ ) {            
         if( textoParaBuscar.equals( textoEnQueBuscar.substring( k, k + longPalabra ) ) ) {
            return true;
         }
      }
   }
   return false;
}

El funcionamiento es bastante sencillo, en ambos métodos, los for externos se usan para determinar el largo de la subcadena, empezando de la más larga posible y acortando hasta llegar a un tamaño de "4".
En el for interno, vamos generando las subcadenas, partiendo desde "k" hasta "k" más el largo que nos determina el for externo.
Lo que resta es hacer las comparaciones, en caso de haber coincidencias se quita la cadena encontrada del texto recibido y se vuelve a llamar al método con la nueva cadena.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.