⽤Java求两个字符串所有的公共⼦序列package test;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class ExactAllCommonSeq {
/**
* 求取两个字段所有的⼦序列
* @param inputA
* @param inputB
* @return
*/
public static List<String> exactAllCommonSeq(String inputA, String inputB) {
//把字符串转成字符数组
char[] arr1 = CharArray();
char[] arr2 = CharArray();
// 把两个字符串分别以⾏和列组成⼀个⼆维矩阵
int[][] temp = new int[arr1.length][arr2.length];
//初始化⼆维矩阵中的第⼀⾏
for (int i = 0; i < arr2.length; i++) {
temp[0][i] = (arr1[0] == arr2[i]) ? 1 : 0;
}
/
/初始化⼆维矩阵中的第⼀列
for (int j = 0; j < arr1.length; j++) {
temp[j][0] = (arr2[0] == arr1[j]) ? 1 : 0;
}
//嵌套for循环：⽐较⼆维矩阵中每个点对应⾏列字符中否相等，相等的话值设置为1，否则设置为0
for (int i = 1; i < arr1.length; i++) {
for (int j = 1; j < arr2.length; j++) {
if (arr1[i] == arr2[j]) {
//对⾓线上⼀个值加1，⽅便求取每个公共⼦序列的长度
temp[i][j] = temp[i - 1][j - 1] + 1;
} else {
temp[i][j] = 0;
}
}
}
List<Map<String, Integer>> list = new ArrayList<>();
//依次遍历对⾓矩阵的对⾓线
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr2.length; j++) {
Map<String, Integer> map = new HashMap<>();
if (temp[i][j] != 0 && temp[i][j] != 1) {
if (temp[i - 1][j - 1] == temp[i][j] - 1) {
if (i - 1 > 0 && j - 1 > 0 && i + 1 < arr1.length && j + 1 < arr2.length && temp[i - 1][j - 1] != 0 && temp[i + 1][j + 1] == 0) {                            map.put("row", i);
map.put("column", j);
map.put("length", temp[i][j]);
list.add(map);
子字符串是什么} else if ((i + 1 == arr1.length || j + 1 == arr2.length)) {
map.put("row", i);
map.put("column", j);
map.put("length", temp[i][j]);
list.add(map);
}
}
}
}
}
List<String> resultList = new ArrayList<>();
if (!list.isEmpty()) {
for (Map<String, Integer> map : list) {
String s = getsubString(inputA, ("row"), ("length"));
resultList.add(s);
}
}
return resultList;
}
/**
* 根据坐标位置及⼦串长度获取⼦串内容
* @param s
* @param a
* @param b
* @return
*/
public static String getsubString(String s, int a, int b) {
String s1 ;
s1 = s.substring(a - b + 1, a + 1);
return s1;
}
/**
* 测试⽅法
* @param args
*/
public static void main(String[] args) {
String inputA = "我爱你，中国";
String inputB = "我爱你，我是中国⼈";
System.out.println(exactAllCommonSeq(inputA, inputB));    }
}
输出结果：
[我爱你，, 中国]

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。