Common Subsequence POJ - 1458 (最长公共子串)

痛定思痛。 2022-02-25 02:04 230阅读 0赞

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, x ij= 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

求最长公共子串问题:

令dp\[i\]\[j\]表示字符串S1的前i号位和S2的前j号位的最长公共子串,比如dp\[3\]\[4\]表示

abc和abfc的最长公共子串,长度为3,根据A\[i\]和B\[j\],可以分为两种决策:

A\[i\] == B\[j\]

比如dp\[3\]\[4\]为 abc和abfc之间的比较,可见末尾都为c,那么结果是dp\[2\]\[3\]状态的长度再加上1

A\[i\] != B\[j\]

比如dp\[4\]\[4\]为abcf和abfc之间的比较,可见末尾字符值不一致,那么我们比较 abc abfc状态 和 abcf abf状态的公共子串长度更长,将长度保存到dp\[4\]\[4\]种

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <string.h>
    using namespace std;
    const int MAXN = 1010;
    int sdp[MAXN][MAXN];
    string S1, S2;
    int main() {
    	while (cin >> S1 >> S2) {  //数据读入
    		int len1 = S1.length();
    		int len2 = S2.length();  
    		memset(sdp, 0, sizeof(sdp));  //全部初始化为0
    		for (int i = 1; i <= len1; ++i) {  //字符串S1
    			for (int j = 1; j <= len2; ++j) {
    				if (S1[i-1] == S2[j-1]) {   //为什么i-1,j-1?因为是从S1,S2,是从0开始的,而状态是从1开始的
    					sdp[i][j] = sdp[i - 1][j - 1] + 1;  
    				}
    				else {
    					sdp[i][j] = max(sdp[i - 1][j], sdp[i][j - 1]); //左右两种情况较大的那一种
    				}
    			}
    		}
    		cout << sdp[len1][len2] << endl;
    	}
    	system("PAUSE");
    	return 0;
    }