耿教师教你学Java：两个字符序列的最长公共子序列
两个字符序列的最长公共子序列
耿祥义
那里所说的一个字符序列的子序列是指那个字符序列从某个索引位置起头，到某个索引位置完毕的持续个字符所构成的序列。
关于
Strings1 = "123found89",
s2 = "89javafound5";
二者的最长公共子序列是"found",其长度为5。本文的算法实现里用到了参数形式，即除了返回更大值，还需要笔录子序列在各自字符序列里呈现的位置
1.算法
我们定义一个二维数组
int [ ][ ] a = new int[ m][ n];
此中m,n是两个字符序列s1和s2的长度。
算法描述如下：
（1）起首计算二维数组的单位的值（算法复杂度是O(m*n)）
if(s1.charAt(i) == s2.charAt(j))
a[i][j] = 1+a[i-1][j-1];
else
a[i][j] = 0;
算法的关键是假设s1第i个位置上的字符和s2第j个位置上的字符不异，就要察看各自前一个位置上的字符能否相等，即a[i][j]的值笔录了s1截行到第i个位置和s2截行到第j个位置，二者持续呈现的相等字符的次数（所以需要 a[i][j] = 1+a[i-1][j-1];）。
（2） 找出二维数组的更大值所在的单位（算法复杂度是O(m*n)）
二维数组中 单位的更大值就是两个字符序列的最长公共子序列的长度，该单位的行索引就是公共子序列在s1中的完毕位置，该单位的列索引就是公共子序列在s2中的完毕位置。
（3）输出更大值，根据更大值单位的行索引或列索引输出s1，s2的更大公共子序列。
★ 关于前面的"123found89"，"89javafound5"
● 二维数组a是：
●更大值5是最长公共子序列的长度，其所在的单位是a[7][10] （重视,索引从0起头），此中行索引7是公共子序列在s1，即 "123found89" 中的完毕位置；列索引10是公共子序列在s2，即"89javafound5"中的完毕位置。
●更大公共子序列"found"在s1,"123found89"呈现的位置是从3到7，在s2,"89javafound5"呈现的位置是从6到10。
2.代码与效果
那里用到参数形式，除了返回更大值，还需要笔录子序列的位置，参数形式见后面的选举阅读
FindMax.java
import java.util.Arrays;
public class FindMax {
public static int findMaxCommon(String s1,String s2,int [] index){ //查找s1和s2更大公共子序列
int m = s1.length,
n = s2.length;
int [][] a= new int[m][n];
for(int i=0;im;i++) {
for(int j=0;jn;j++) {
if(s1.charAt(i)==s2.charAt(j)){
if(i0j0){
a[i][j] = 1+a[i-1][j-1];
else{
a[i][j] = 1;//下标越界就不消累计。
else {
a[i][j]=0;
for(int i=0;im;i++) { //能够不输出，那里是为了进修的曲看
System.out.println(Arrays.toString(a[i]));
int max = 0;
for(int i=0;im;i++) { //觅觅数组中的更大值
for(int j=0;jn;j++) {
if(a[i][j]max) {
max = a[i][j];
index[0] =i;
index[1] =j;
return max;
MainClass.java
public class MainClass{
public static void main(String args[]) {
String s1 = "123bird89",
s2 = "89flybird5";
int index[] ={-1,-1};//用于存放子序列呈现的索引位置
int max =FindMax.findMaxCommon(s1,s2,index);
if(max0) {
System.out.println("最长公共子序列长度"+max);
System.out.println("在"+s1+"完毕位置是"+index[0]);
System.out.println("在"+s2+"完毕位置是"+index[1]);
System.out.print("最长公共子序列是:");
System.out.println(s1.substring(index[0]-max+1,index[0]+1));
else {
System.out.println("没有公共子序列");
参数存值形式与标致的项链
耿祥义次要教材源代码暨习题解答下载