最长公共子序列(Longest Common Subsequence)定义:两个或多个已知数列的子序列集合中最长的就是最长公共子序列。其实说到最长公共子序列,还有一个要提到的是最长公共子串(Longest Common Substring),它指的是两个字符串中的最长公共子串,要求子串一定连续。关于最长公共子串的内容我们后续也会讲到,今天先来看下最长公共子序列的相关内容。
之前看过一个LCS算法的实现过程,觉得太过繁琐。自己写了一个比较简单的,此处仅仅介绍实现过程。
程序代码测试通过,需要的童鞋可以在这里拷贝一下,代码如下:
package com.wsy.dynamic; import java.util.HashMap; import java.util.Map; public class ImpLCS { public String getLCS(String str1, String str2, int n, int m){ validate(str1, str2); char[] a = str1.toCharArray(); char[] b = str2.toCharArray(); int[][] c = new int[n+1][m+1]; //存放序列 Mapmap = new HashMap (); //初始化参数 for(int i = 0;i<=n;i++){ c[i][0] = 0; map.put(i + "0", ""); } for(int i = 0;i<=m;i++){ c[0][m] = 0; map.put("0" + i, ""); } for(int i = 1;i<=n;i++){ for(int j = 1;j<=m;j++){ if(a[i-1] == b[j-1]){ c[i][j] = c[i-1][j-1] + 1; String tmp = map.get(changeNum(i-1,j-1)); map.put(changeNum(i,j), tmp + String.valueOf(a[i-1])); }else{ if(c[i][j-1] > c[i-1][j]){ c[i][j] = c[i][j-1]; String tmp = map.get(changeNum(i,j-1)); map.put(changeNum(i,j), tmp); }else{ c[i][j] = c[i-1][j]; String tmp = map.get(changeNum(i-1,j)); map.put(changeNum(i,j), tmp); } } } } String key = changeNum(n,m); return map.get(key); } /** * 将数字拼接成字符串 * @param i * @param j * @return */ private String changeNum(int i, int j) { StringBuilder sb = new StringBuilder(String.valueOf(i)); return sb.append(j).toString(); } /** * 验证参数 * @param str1 * @param str2 */ private void validate(String str1, String str2) { // 略 } public static void main(String[] args) { ImpLCS lcs = new ImpLCS(); String rs = lcs.getLCS("12345", "12334", 5, 4); System.out.println("---:" + rs); } }
忍者必须死34399账号登录版 最新版v1.0.138v2.0.72
下载勇者秘境oppo版 安卓版v1.0.5
下载忍者必须死3一加版 最新版v1.0.138v2.0.72
下载绝世仙王官方正版 最新安卓版v1.0.49
下载Goat Simulator 3手机版 安卓版v1.0.8.2
Goat Simulator 3手机版是一个非常有趣的模拟游
Goat Simulator 3国际服 安卓版v1.0.8.2
Goat Simulator 3国际版是一个非常有趣的山羊模
烟花燃放模拟器中文版 2025最新版v1.0
烟花燃放模拟器是款仿真的烟花绽放模拟器类型单机小游戏,全方位
我的世界动漫世界 手机版v友y整合
我的世界动漫世界模组整合包是一款加入了动漫元素的素材整合包,
我的世界贝爷生存整合包 最新版v隔壁老王
我的世界MITE贝爷生存整合包是一款根据原版MC制作的魔改整