- 从磁盘中读取两个文件
将两个序列分别记为X和Y,X序列元素分别为{x1,x2……,xn},Y序列元素分别为{y1,y2,……ym},,
- 用一个char类型的数组来存放这两个字符串
- 用一个二维数组arr[][]来存放公共字符串的长度
- 先给这个数组的行列进行初始化
- 计算arr的其他元素
如果xi == yj, 则 arr[i][j] = arr[i-1][j-1]+1
如果xi ! = yj, 那么arr[i][j] = 0
- 记录最长公共字符串的长度lmax 记录最长公共字符串结束的位置pmax
- 找到最长的lmax,lmax对应的i就是要找的pmax
- 根据lmax和pmax就可以确定两个文件相同的内容和最长公共字符串
- 比较两个字符串的相似度
公共子序列与公共子串不同在于子序列不要求连续。将原问题分解成子问题,而且子问题的最优解最终组成整个问题的最优解,也就是说该问题具备最优子结构性质
利用一个二维数组进行求解,arr数组负责存值,求得公共字符的最大长度
实验代码:
/* 动态规划-最长公共字符串 问题
输入:
磁盘上有两个文件,程序运行时输入两个文件的名称,比对两个文件中最长公共子串。
并输出两个文件共同的内容及两个文件的近似度(用百分比表示)。*/
package cn.bxit.ALg;
import java.io.*;
import java.util.Scanner;
public class publicString {
public static void main(String[] args) {
int lmax = 0;// 记录最长公共字符串的长度
int pmax = 0;// 记录最长公共字符串结束的位置
//1.从磁盘中读取两个文件
Scanner scan = new Scanner(System.in);
System.out.println("填写文件地址如填写文件地址如C:\\\\Users\\\\HX\\\\Desktop\\\\xuexi\\\\untitled\\\\src\\\\txt1.txt");
System.out.print("请输入第一个文件地址:");// 填写文件地址如C:\\Users\\HX\\Desktop\\xuexi\\untitled\\src\\txt1.txt
// String str1 = getFile(scan.next());
String str1=scan.next();
System.out.print("请输入第二个文件地址:");// 填写文件地址如C:\\Users\\HX\\Desktop\\xuexi\\untitled\\src\\txt1.txt
String str2=scan.next();
// String str2 = getFile(scan.next());
//2.用一个char类型的数组来存放这两个字符串
char char1[] = str1.toCharArray();
char char2[] = str2.toCharArray();
//3.用一个二维数组arr[][]来存放公共字符串的长度
int[][] arr = new int[str1.length()][str2.length()];
//4.先给这个数组的行列进行初始化
// 4.1行初始化
for (int j = 0; j < str2.length(); j++) {
if (char2[j] == char1[0]) {
arr[0][j] = 1;
}
}
// 4.2列初始化
for (int i = 0; i < str1.length(); i++) {
if (char1[i] == char2[0]) {
arr[i][0] = 1;
}
}
//4.3.计算arr的其他元素
for (int i = 1; i < str1.length(); i++) {
for (int j = 1; j < str2.length(); j++) {
if (char1[i] == char2[j]) {
arr[i][j] = arr[i - 1][j - 1] + 1;
} else {
arr[i][j] = 0;
}
}
}
// 5.找到最长的lmax,lmax对应的i就是要找的pmax
for (int i = 0; i < str1.length(); i++) {
for (int j = 0; j < str2.length(); j++) {
if (arr[i][j] > lmax) {
lmax = arr[i][j];
pmax = i;
}
}
}
//6.输出这个公共的字符串
if (lmax == 0) {
System.out.println("这个文件中没有公共字符串!");
} else {
System.out.print("这个最长公共字符串是:");
for (int i = pmax - lmax + 1; i <= pmax; i++) {
System.out.print(char1[i]);
}
System.out.println();
}
//7.比较两个字符串的相似度
// 7.1获取哪个长的字符串的长度
int stringMax = (str1.length() > str2.length()) ? str1.length() : str2.length();
double simarity = (double) lmax / stringMax * 100;// 两个字符串的相似度
System.out.println("这两个字符串的相似度为:" + simarity + "%");
}
//获取文件
public static String getFile(String txt) {
int num = 0;
String buf = "";
// 打开文件
String l = null;
try {
BufferedReader r = new BufferedReader(new InputStreamReader(new FileInputStream(txt), "Utf-8"));
while ((l = r.readLine()) != null) {
buf += l + "\n";
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
return buf;
}
}
运行结果: