QBSTR – Xâu con chung dài nhất

package practice;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
/*
* https://vn.spoj.com/problems/QBSTR/
*
*/
public class XauConChungDaiNhat {
static String s1, s2;
static int[][] a = new int[1002][1002];

public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream(“XauConChungDaiNhat.txt”));
Scanner sc = new Scanner(System.in);
s1 = sc.nextLine();
s2 = sc.nextLine();
int n1 = s1.length();
int n2 = s2.length();
// co so quy hoach dong
// hang
for (int i = 0; i <= n2; i++) {
a[0][i] = 0;
}
// cot
for (int i = 0; i <= n2; i++) {
a[0][i] = 0;
}
for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
if (s1.charAt(i) == s2.charAt(j)) {
a[i + 1][j + 1] = a[i][j] + 1;
} else {
a[i + 1][j + 1] = Math.max(a[i + 1][j], a[i][j + 1]);
}
}
}

// for (int i = 0; i <= n1; i++) {
// for (int j = 0; j <= n2; j++) {
// System.out.print(a[i][j]+” “);
// }
// System.out.println();
// }
System.out.println(a[n1][n2]);
}

}

Advertisement