首页 > 代码库 > 字符串最长公共子序列问题
字符串最长公共子序列问题
找两个字符串的最长公共子序列，最长公共子序列并不要求连续。
代码如下：
package string;import java.util.ArrayList;import java.util.List;/** * 字符串的最长公共子序列问题 * @author Administrator * */public class LCSequence { /** * 求最长公共子序列长度 * @param s1 * @param s2 * @return */ public int getMaxLCSLen(String s1, String s2){ int maxLen = 0; if(s1 == null || s2 == null){ return maxLen; } int m = s1.length(); int n = s2.length(); // a[i][j]记录s1[0~i-1]与s2[0~j-1]的最长公共子序列长度 int[][] a = new int[m+1][n+1]; for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ if(s1.charAt(i-1) == s2.charAt(j-1)){ a[i][j] = Math.max(a[i][j-1], a[i-1][j-1] + 1); a[i][j] = Math.max(a[i][j], a[i-1][j]); }else{ a[i][j] = Math.max(a[i][j-1], a[i-1][j]); } maxLen = Math.max(maxLen, a[i][j]); } } return maxLen; } /** * 求最长公共子序列 * @param s1 * @param s2 * @return */ public List<String> getMaxLCS(String s1, String s2){ int maxLen = 0; List<String> res = new ArrayList<String>(); if(s1 == null || s2 == null){ return res; } int m = s1.length(); int n = s2.length(); // a[i][j]记录s1[0~i-1]与s2[0~j-1]的最长公共子序列长度 int[][] a = new int[m+1][n+1]; for(int i = 1; i <= m; i++){ for(int j = 1; j <= n; j++){ if(s1.charAt(i-1) == s2.charAt(j-1)){ a[i][j] = Math.max(a[i][j-1], a[i-1][j-1] + 1); a[i][j] = Math.max(a[i][j], a[i-1][j]); }else{ a[i][j] = Math.max(a[i][j-1], a[i-1][j]); } if(a[i][j] == maxLen){ String s = s1.substring(i-a[i][j], i); if(!res.contains(s)){ res.add(s); } } else if(a[i][j] > maxLen){ maxLen = a[i][j]; res = new ArrayList<String>(); res.add(s1.substring(i-a[i][j], i)); } } } return res; } public static void main(String[] args) { LCSequence lcs = new LCSequence(); String s1 = "a1b2c3"; String s2 = "1a1wbz2c123a1b2c123"; System.out.println(lcs.getMaxLCSLen(s1, s2)); System.out.println(lcs.getMaxLCS(s1, s2)); }}
字符串最长公共子序列问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。