poj 1458 Common Subsequence(dp)
2024-09-03 13:49:38
Common Subsequence
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 46630 | Accepted: 19154 |
Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
Input
The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.
Output
For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
0
Java AC 代码:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in);
String first = "";
String second = "";
while(!(first = sc.next()).equals("") && !(second = sc.next()).equals("")) {
char[] firstArray = first.toCharArray();
char[] secondArray = second.toCharArray();
int firstLen = first.length();
int secondLen = second.length();
int[][] subMaxLen = new int[firstLen + 1][secondLen + 1]; //这里设置成长度加1的,是为了防止下面 i-1 j-1的时候数组越界。
for(int i = 1; i <= firstLen; i++)
for(int j = 1; j <= secondLen; j++) {
if(firstArray[i - 1] == secondArray[j - 1])
subMaxLen[i][j] = subMaxLen[i - 1][j - 1] + 1;
else
subMaxLen[i][j] = (subMaxLen[i - 1][j] > subMaxLen[i][j - 1] ? subMaxLen[i - 1][j] : subMaxLen[i][j - 1]);
}
System.out.println(subMaxLen[firstLen][secondLen]);
} } }
最新文章
- OSI七层模型
- Openjudge 1.13.37:乒乓球
- nginx 报错 HTTP ERROR 500 (PHP数组简写模式)
- 收藏的几个经典Flash
- swift基础:第四部分:对函数和闭包的深入
- Volatile实现原理
- IOC基础
- HTTP协议 概述
- NGINX实现IF语句里的AND,OR多重判断
- android判断文件是否是图片文件的方法
- ST-2
- Spring Data(一)概念和仓库的定义
- 动态规划 Common Subsequence
- Odoo 12 开发手册指南(八)—— 业务逻辑 – 业务流程的支持
- ssh登录错误ECDSA host key for ip has changed解决方案
- 洛谷P2756 飞行员配对方案问题
- 带着萌新看springboot源码06
- c++ 调用 wmi 获取数据
- hdu1272 小希的迷宫(并查集)
- Python学习--14 序列化