Written by razrlele
17:39 February 1, 2016
Common Subsequence
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 44778 | Accepted: 18346 |
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
|
1 2 3 |
abcfbc abfcab programming contest abcd mnp |
Sample Output
|
1 2 3 |
4 2 0 |
Source
思路
题目的意思就是给定两个字符串S1、S2，定义子串中的每一个元素都能够在父串中找到并且顺序一致（但是不要求在父串中连续）。
用一个二维数组MAXLEN[i][j]记录长度为i的S1前缀和长度为j的S2前缀的最长公共字串，然后就可以得到递推关系：
if S1[i] == S2[j]
MAXLEN[i][j] = MAXLEN[i-1][j-1] + 1;
else
MAXLEN[i][j] = max( MAXLEN[i][j-1], MAXLEN[i-1][j]);
题目所求的就是MAXLEN[ S1.length() ][ S2.length() ]， 这样就可以在O(m*n)的复杂度下解决了。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
/* * File Name: poj1458.cpp * Author: razrLeLe * Mail: razrlele@gmail.com */ #include <vector> #include <set> #include <deque> #include <queue> #include <algorithm> #include <functional> #include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <string> #include <cstring> #include <string.h> #include <map> #include <cctype> #include <list> #include <stack> #define forn(i, m, n) for( int i = int(m); i < int(n); i++ ) typedef long long ll; using namespace std; #define INF 0x3f3f3f3f #define LOCAL const int maxn = 1001; int main(int argc, char ** argv) { #ifdef LOCAL freopen("/home/razrlele/build/data.txt", "r", stdin); freopen("/home/razrlele/build/out.txt", "w", stdout); #endif int MAXLEN[maxn][maxn]; string a, b; while( cin >> a >> b ){ int lena = a.length(), lenb = b.length(); forn(i, 0, lena+1){ MAXLEN[i][0] = 0; } forn(i, 0, lenb+1){ MAXLEN[0][i] = 0; } forn(i, 1, lena+1) forn(j, 1, lenb+1 ){ if( a[i-1] == b[j-1] ) MAXLEN[i][j] = MAXLEN[i-1][j-1] + 1; else MAXLEN[i][j] = max( MAXLEN[i-1][j], MAXLEN[i][j-1] ); } cout << MAXLEN[lena][lenb]<<endl;; } return 0; } |