## 最长公共子序列 原

a_xianyu

from: http://acm.nyist.net/JudgeOnline/problem.php?pid=36

第一行给出一个整数N(0<N<100)表示待测数据组数
接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000.

每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。

```2
asdf
123abc
abc123abc```

```3
6```

Solution:

``````import java.io.BufferedReader;
import java.io.IOException;

/**
* @create 2017-09-04 8:51
*/
public class Main {
public static int longestCommonSubstring(String s1, String s2) {
if (s1 == null || s2 == null) {
return 0;
}

int[][] m = new int[s1.length() + 1][s2.length() + 1];
//初始化边界条件
for (int i = 0; i <= s1.length(); i++) { //每行第一列置0
m[i][0] = 0;
}
for (int j = 0; j <= s2.length(); j++) { //每列第一行置0
m[0][j] = 0;
}

int result = 0;
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
m[i][j] = m[i - 1][j - 1] + 1;
} else {
m[i][j] = Math.max(m[i - 1][j], m[i][j - 1]);
}
result = Math.max(m[i][j], result);
}
}

return result;
}

public static void main(String[] args) throws IOException {
while (n-- > 0) {
}
br.close();
}
}``````

要想把最长的公共字串打印出来，还是贴代码，直接看结果

``````import java.io.BufferedReader;
import java.io.IOException;

/**
* @create 2017-09-04 8:51
*/
public class Main {
public static String s1, s2;

public static int[][] longestCommonSubstring() {
if (s1 == null || s2 == null) {
return null;
}

int[][] m = new int[s1.length() + 1][s2.length() + 1];
//初始化边界条件
for (int i = 0; i <= s1.length(); i++) { //每行第一列置0
m[i][0] = 0;
}
for (int j = 0; j <= s2.length(); j++) { //每列第一行置0
m[0][j] = 0;
}

for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
m[i][j] = m[i - 1][j - 1] + 1;
} else {
m[i][j] = Math.max(m[i - 1][j], m[i][j - 1]);
}
}
}

return m;
}

public static void printLCS(int[][] m, int i, int j) {//打印最长公共子序列
if (i == 0 || j == 0) {
return;
}
//        System.out.println("i=" + i + ", j=" + j);
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
printLCS(m, i - 1, j - 1);
System.out.print(s1.charAt(i - 1));
} else if (m[i-1][j] >= m[i][j]){
printLCS(m, i - 1, j);
} else {
printLCS(m, i, j - 1);
}
}

public static void print(int[][] m) {   //打印矩阵
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < m[i].length; j++) {
if (i == 0 && j == 0) {
System.out.print("* ");
} else if (i == 0) {
System.out.print(s2.charAt(j - 1) + " ");
} else if (j == 0) {
System.out.print(s1.charAt(i - 1) + " ");
} else {
System.out.print(m[i][j] + " ");
}
}
System.out.println();
}
}
public static void main(String[] args) throws IOException {
while (n-- > 0) {

int[][] m = longestCommonSubstring();
print(m);
printLCS(m, s1.length(), s2.length());
System.out.println();
}
br.close();
}
}``````

``````1
asdf
asfsd``````

``````* a d f s d
a 1 1 1 1 1
s 1 1 1 2 2
d 1 2 2 2 3
f 1 2 3 3 3
asd``````

ps: 要想查看打印过程，将printLCS的第一个System.out.println的注释取消，将第二个System.out.print的注释加上

### a_xianyu

#### 暂无文章

CentOS配置Tomcat监听80端口,虚拟主机

Tomcat更改默认端口为80 更改的配置文件是: /usr/local/tomcat/conf/server.xml [root@test-a ~]# vim /usr/local/tomcat/conf/server.xml # 找到 Connector port="8080" protocol="HTTP/1......

5
0
《稻盛和夫经营学》读后感心得体会3180字范文

《稻盛和夫经营学》读后感心得体会3180字范文： 一代日本经营之圣稻盛和夫凭借刻苦勤奋的精神以及深植于佛教的商业道德准则，成为了“佛系”企业家的代表人物。在《稻盛和夫经营学》“领导人...

3
0
java框架学习日志-5（常见的依赖注入）

4
0

mbzhong

2
0
ActiveMQ消息传送机制以及ACK机制详解

AcitveMQ是作为一种消息存储和分发组件，涉及到client与broker端数据交互的方方面面，它不仅要担保消息的存储安全性，还要提供额外的手段来确保消息的分发是可靠的。 一. ActiveMQ消息传送机...

watermelon11

2
0