Java - SUBSECUENCIA COMUN MAS LARGA

   
Vista:

SUBSECUENCIA COMUN MAS LARGA

Publicado por Kurt (55 intervenciones) el 23/11/2010 17:41:04
HOLA

Me gustaria que me explicaran como hacer un algoritmo para sacar la subsecuencia comun mas larga, o si me pudieran facilitar el algoritmo
Muchas gracias
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

SUBSECUENCIA COMUN MAS LARGA

Publicado por Jorge Díaz (1 intervención) el 04/06/2017 19:22:22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
/*
Input: XMJYAUZ MZJAWXU 
Output: MJAU
*/
 
class LCS {
 
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 
		String cadena;
		while ((cadena = in.readLine()) != null) {
 
			String array[] = cadena.split(" ");
			int n = array[0].length() > array[1].length() ? array[0].length() : array[1].length();
 
			// Llenar la matriz según las letras comunes
			int[][] matrix = new int[n][n];
			for (int i = 0; i < array[0].length(); i++)
				for (int j = 0; j < array[1].length(); j++)
					if (array[0].charAt(i) == array[1].charAt(j))
						matrix[i][j]++;
 
			// Encontrar la subsecuencia común más larga
			String palabraRepetida = "";
			for (int i = 0; i < matrix.length >> 1; i++) {
				String nuevo = "";
				for (int j = i, restriccion = -1; j < matrix.length; j++)
					for (int k = 0; k < matrix.length; k++)
						if (matrix[j][k] == 1 && restriccion < k) {
							nuevo += array[0].charAt(j);
							restriccion = k;
							break;
						}
				if (palabraRepetida.length() < nuevo.length())
					palabraRepetida = nuevo;
			}
 
			System.out.println(palabraRepetida);
		}
	}
 
}
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar