package com.parser.main;
import java.util.ArrayList;
import java.util.List;
//LCS算法实现 求两个字符串中间最长的公共字符串
public class Ss {
public static void main(String[] args) {
Ss ss = new Ss();
ss.getSameStr("12", "123pdg123");
}
public List<String> getSameStr(String str1, String str2){
char[] arrchar1 = str1.toCharArray();
char[] arrchar2 = str2.toCharArray();
int[][] arr = new int[arrchar1.length][arrchar2.length];
int len = arrchar1.length < arrchar2.length ? arrchar1.length:arrchar2.length;
int maxarr[] = new int[len];
int maxindex[] = new int[len];
for(int i = 0; i < arrchar1.length ; i++){
for(int j = 0; j < arrchar2.length ; j++){
if(arrchar2[j] == arrchar1[i]){
if(i == 0 || j == 0){
arr[i][j] = 1;
if(maxarr[0] < 1){
maxarr[0] = 1;
maxindex[0] = i;
}
}else{
arr[i][j] = arr[i-1][j-1] + 1;
//如果当前求出的子串长度大于了maxarr中第一个数值 则清空maxarr数值 全部置0 同时替换第一个最大值
if(maxarr[0] < arr[i][j]){
maxarr[0] = arr[i][j];
maxindex[0] = i;
for(int num = 1; num < maxarr.length; num++){
if(maxarr[num] == 0){
break;
}else{
maxarr[num] = 0;
maxindex[num] = 0;
}
}
}else if (maxarr[0] == arr[i][j]){
//如果当前求出的子串长度跟maxarr中第一个一致 则保留
int num = 0;
for(int max : maxarr){
if(max == 0){
maxarr[num] = arr[i][j];
maxindex[num] = i;
break;
}
num++;
}
}
}
}else{
arr[i][j] = 0;
}
}
}
for(int i = 0;i < arr.length ; i++){
for(int j = 0;j < arr[i].length;j++){
System.out.print(" " + arr[i][j]);
}
System.out.println("");
}
List<String> list = new ArrayList<String>();
for(int i = 0; i< maxarr.length ;i++){
if(maxarr[i] == 0){
break;
}
int num = maxindex[i] - (maxarr[i] -1);
String str = "";
for(int k = 0;k<maxarr[i];k++){
char tempchar = arrchar1[num];
str += String.valueOf(tempchar);
num++;
}
System.out.println(str);
list.add(str);
}
return list;
}
}
分享到:
相关推荐
最长公共字串算法,为算法导论上的算法,可以运行,运行时间为O(mn)
LCS 最长公共子序列 用JAVA实现,直接导入可运行,实例可以另外自己定义
动态规划:最长公共子串 LCS 动态规划:最长公共子串 LCS
根据LCS算法取出最长公用字符串,实现字符串比较
LCS最长公共子序列,完全正确的C++代码!
c源码编写的求两个字符串的最长公共子串,采用递归算法
MFC实现数据结构的简单问题,最长公共子串,界面良好,算法简单
关于LCS(最长公共子序列)算法的实现~ 自己测试通过的
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
最长子序列LCS算法,用于处理最长公共字串问题。 两个序列的LCS问题包含两个序列的前缀的LCS,因此,LCS问题具有最优子结构性质。在设计递归算法时,不难看出递归算法具有子问题重叠的性质。 设C[i,j]C[i,j]...
实现了求最长公共子序列的算法,内容简单易懂,代码也很短
LCS算法的简单java实现,可以一起讨论学习
若ai≠bj,回溯到左上角、上边、左边中值最小的单元格,若有相同最小值的单元格,优先级按照左上角、上边、左边的顺序 若当前单元格是在矩阵的第一行,则回溯至左边的单元格 若当前单元格是在矩阵的第一列,则回溯...
用c++编写的最长公子序列的源代码 如果有多个结果会输出所有的结果
最长公共子序列问题 for ( i = 0; i ; i++) { c[i] = new int[n+1]; } for(i=0;i;i++) {c[i][0]=0;b[i][0]=0;} for(i=0;i;i++) {c[0][i]=0;b[0][i]=0;} for(i=1;i;i++) for(j=1;j;j++) if(s1[i-1]==s2[j...
最长公共子序列算法LCS实现。任意输入两个字符串,通过此算法可以找到最长的公共子序列。
采用动态规划法与回溯法实现了lcs算法,并显示各算法运行时间,便于对不同的输入数据测试这两个算法的优劣。
最长公共子序列(LCS)算法实验 最长公共子序列(LCS)算法实验 最长公共子序列(LCS)算法实验
LCS算法的精髓就是动态规划,序列其实不仅限于字符序列,因此我用模版类对该算法进行了封装,里面提供了尽量方便的函数来进行该算法的使用,该实现并不追求速度最快化,而是尽量让该算法类能支持重用,若发现算法有...
LCS最长公共子序列c++的代码。动态规划思想