package workfour;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.util.Random;
public class LCS {
private static int z=0;
private static char[] a= new char[100];
public static void main(String[] args) throws Exception {
//随机生成指定长度的字符串
int size = 20;
String x = generateRandomStr(size);
String y = generateRandomStr(size);
int m = x.length();
int n = y.length();
File file = new File("D:\\input.txt");
FileWriter outputStream;
try {
outputStream = new FileWriter(file);
String content = String.valueOf(x) + "";
outputStream.write(content+"\t");
String content1 = String.valueOf(y) + "";
outputStream.write(content1+"\t");
outputStream.close();
} catch (Exception e) {
e.printStackTrace();
}
String filePath = "D:/input.txt";
FileInputStream fin = new FileInputStream(filePath);
InputStreamReader reader = new InputStreamReader(fin);
BufferedReader buffReader = new BufferedReader(reader);
String strTmp = "";
while((strTmp = buffReader.readLine())!=null){
System.out.println(strTmp + "\n");
}
buffReader.close();
//创建二维数组，也就是填表的过程
int[][] c = new int[m+1][n+1];
//初始化二维数组
for (int i = 0; i < m+1; i++) {
c[i][0] = 0;
}
for (int i = 0; i < n+1; i++) {
c[0][i] = 0;
}
//实现公式逻辑
int[][] path = new int[m+1][n+1];//记录通过哪个子问题解决的，也就是递推的路径
for (int i = 1; i < m+1; i++) {
for (int j = 1; j < n+1; j++) {
if(x.charAt(i-1) == y.charAt(j-1)){
c[i][j] = c[i-1][j-1] + 1;
}else if(c[i-1][j] >= c[i][j-1]){
c[i][j] = c[i-1][j];
path[i][j] = 1;
}else{
c[i][j] = c[i][j-1];
path[i][j] = -1;
}
}
}
//输出查看c
System.out.println("c:");
for (int i = 0; i < m+1; i++) {
for (int j = 0; j < n+1; j++) {
System.out.print(c[i][j]+"\t");
}
System.out.println();
}
System.out.println("最长公共子序列的个数："+c[m][n]);
System.out.printf("%s与%s的最长公共子序列为：\n",x,y);
PrintLCS(path,x,m,n);
File files = new File("d:\\output.txt");
FileOutputStream outputStream1;
try {
outputStream1 = new FileOutputStream(files);
outputStream1.write(("最长公共子序列长度为："+c[m][n]+"\r\n").getBytes());
outputStream1.write(("最长公共子序列为：").getBytes());
for(int i=0;i<z;i++){
outputStream1.write(String.valueOf(a[i]).getBytes());
}
outputStream1.close();
} catch (Exception e) {
e.printStackTrace();
}
}
public static String generateRandomStr(int length) {
String base = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
Random random = new Random();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++) {
int number = random.nextInt(base.length());
sb.append(base.charAt(number));
}
return sb.toString();
}
public static void PrintLCS(int[][]b,String x,int i,int j){
if(i == 0 || j == 0){
return;
}
if(b[i][j] == 0){
PrintLCS(b,x,i-1,j-1);
char c=x.charAt(i-1);
System.out.printf("%c",x.charAt(i-1));
a[z]=c;
z++;
}else if(b[i][j] == 1){
PrintLCS(b,x,i-1,j);
}else{
PrintLCS(b,x,i,j-1);
}
}
}
