UVA10405

UVA10405 URL : http://uva.onlinejudge.org/external/104/10405.pdf




基礎LCS


------------------------------------------------------------------------------------------



import java.util.Scanner;

public class UVA10405 {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);

while(sc.hasNext())
{
String s1 = sc.nextLine();

String s2 = sc.nextLine();

char[] c1 = new char[s1.length()+1];
char[] c2 = new char[s2.length()+1];

for(int s =1;s<s1.length()+1;s++)
{
c1[s] = s1.charAt(s-1);
}

for(int s =1;s<s2.length()+1;s++)
{
c2[s] = s2.charAt(s-1);
}

int matrix[][] = new int[1001][1001];

int max = 0;

for(int n = 1;n<s1.length()+1;n++)
{
for(int m = 1;m<s2.length()+1;m++)

{
if(c1[n] == c2[m])
matrix[n][m] = matrix[n-1][m-1] + 1;
else
matrix[n][m] = Math.max(matrix[n-1][m], matrix[n][m-1]);

if(max <matrix[n][m])
max = matrix[n][m];
}
}
System.out.println(max);
}
sc.close();
}
}