查找两个字符串a,b中的最长公共子串
描述 |
详细描述:
接口设计及说明: /*****************************************************************************
|
---|---|
知识点 | 字符串 |
运行时间限制 | 10M |
内存限制 | 128 |
输入 |
输入两个字符串 |
输出 |
返回重复出现的字符 |
样例输入 | abcdefghijklmnop abcsafjklmnopqrstuvw |
样例输出 | jklmnop |
实现方法:
该问题是一个动态规划问题,个人在网上学习了很久,最后找到了一种普适性的解法。
第一步:先将输入的字符串更改为一行和一列,组成一个矩阵;
第二步:给矩阵赋值。如果矩阵的对应两个字符是相同的,那么我们就给矩阵赋值1,否则赋值0;
第三步:遍历整个二维数组,如果值为1且斜下对角线不为0(也就是1咯),那么就将数值加下去,直到斜对角线下为0时停止;
第四步:回溯后完成整个工作,寻找数组中的最大值,即为最长公共子串的长度;
第五步:可以将最长的公共子串给数出来
上代码:
import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); String str1 = in.next(); String str2 = in.next(); int a = str1.length(); int b = str2.length(); char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int[][] ans = new int [a][b]; for(int i = 0;i < a; i++){ for(int j = 0;j < b; j++){ if(s1[i]==s2[j]){ ans[i][j]=1; } else{ ans[i][j] = 0; } //System.out.print(ans[i][j]+" "); } //System.out.println(); } int tempx,tempy; for(int t = 0;t < a; t++){ for(int r = 0;r < b;r++){ if(ans[t][r]==1){ tempx = t; tempy = r; while(tempx<a-1&&tempy<b-1&&ans[tempx+1][tempy+1]==1){ ans[tempx+1][tempy+1] = ans[tempx][tempy]+1; tempx++; tempy++; } } } } // //注释 // System.out.println(); // System.out.println(); // System.out.println(); // System.out.println(); // System.out.println(); // for(int i = 0;i < a; i++){ // for(int j = 0;j < b; j++){ // System.out.print(ans[i][j]+" "); // } // System.out.println(); // } int max = 0; int indexx=0; int indexy=0; for(int i = 0;i < a;i++){ for(int j = 0;j < b;j++){ if(ans[i][j]>max){ max = ans[i][j]; indexx = i; indexy = j; } } } //System.out.println(max); for(int i = indexx-max+1;i <= indexx; i++){ System.out.print(s1[i]); } System.out.println(); } }
代码运行结果
abcdefghijklmnop abcsafjklmnopqrstuvw
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0
jklmnop