其实就是求解最长公共子序列算法（字丑勿怪）
public static void main(String[]args) {
Scanner scan = new Scanner(System.in);
String a = scan.next();
String b = scan.next();
char a1[][] = new char [1005][16];
char b1[][] = new char [1005][16];
int counta = 1;
int countb = 1;
char aa[] = a.toCharArray();
char bb[] = b.toCharArray();
//第一步 把每个字母都放进二维字符数组中=============================
for(int i =0;i<aa.length;) {
int countaa = 0;
if(aa[i]>='A'&&aa[i]<='Z') {
a1[counta][countaa++] = aa[i];
i++;
if(i==aa.length)
break;
while(aa[i]>='a'&&aa[i]<='z') {
a1[counta][countaa++] = aa[i];
i++;
if(i==aa.length)
break;
}
counta++;}
}
for(int i =0;i<bb.length;) {
int countbb = 0;
if(bb[i]>='A'&&bb[i]<='Z') {
b1[countb][countbb++] = bb[i];
i++;
if(i==bb.length)
break;
while(bb[i]>='a'&&bb[i]<='z') {
b1[countb][countbb++] = bb[i];
i++;
if(i==bb.length)
break;
}
countb++;}
}
//第一步完成==========================================
//第二部动态规划=====================
//状态转移方程
//if(s1[i-1]==s2[j-1]) D[i][j] = 1 + D[i-1][j-1];
//else D[i][j] = max(D[i-1][j],D[i][j-1])
int [][] dp = new int [1005][1005];
for(int i = 1;i<=counta;i++) {
for(int j =1;j<=countb;j++) {
int i1=0;
int j1 = 0;
int index = 0;
while(a1[i][i1]==b1[j][j1]&&a1[i][i1]!=0&&b1[j][j1]!=0) {
i1++;
j1++;
if(a1[i][i1]==0&&b1[j][j1]==0) {
index = 1; //有且只有满足这个条件才是同一个单词，记录一下
}
}
if(index == 1) {
dp[i][j] = dp[i-1][j-1]+1;//动态规划
}
else {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}
}
}
System.out.print(dp[counta][countb]);
}