本文主要是介绍POJ 1458 Common Subsequence 最长公共子序列(LCS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:给出两个字符串,求出最长的公共子序列的长度
Q:什么是公共子序列?
A:子序列中的每个字符都能在两个原串中找到,而且每个字符的先后顺序和原串中的先后顺序一致。
LCS 算法轨迹图
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;public class Main {/*** Q: 为什么这个数组每次使用都不需要清空?* A: 因为数组最上边的一行全部为 0 && 最左边的一列也全部为 0 ,* 而后续的值都是根据这一行一列来定值的。*/private static int[][] maxLen = new int[1000][1000];private static int work(String str, String str2) {char[] ch = str.toCharArray();char[] ch2 = str2.toCharArray();int length = ch.length;int length2 = ch2.length;for (int i = 1; i <= length; i++) {for (int j = 1; j <= length2; j++) {if (ch[i - 1] == ch2[j - 1]) {maxLen[i][j] = maxLen[i - 1][j - 1] + 1;} else {maxLen[i][j] = Math.max(maxLen[i][j - 1], maxLen[i - 1][j]);}}}return maxLen[length][length2];}public static void main(String[] args) {Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));String inputStr;String inputStr2;while (in.hasNext()) {inputStr = in.next();inputStr2 = in.next();out.println(work(inputStr, inputStr2));}out.flush();}
}
这篇关于POJ 1458 Common Subsequence 最长公共子序列(LCS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!