信息学奥赛一本通（1265：【例9.9】最长公共子序列）_1265:【例9.9】最长公共子序列

1265：【例9.9】最长公共子序列

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 10486     通过数: 5509

【题目描述】

【输入】

【输出】

【输入样例】

ABCBDAB
BDCABA

【输出样例】

4

【提示】

【分析】

        设f[i][j]表示序列a[1...i]和b[1...j]的最长公共子序列长度，现在以样例为例，考查末尾元素a[i]与b[j]是否在公共子序列中：

（1）若a[i]=b[j]，则a[i]与b[j]在公共子序列中。

a[1...i-1, i ] → a[1...i-1 ] + a[i]；

b[1...j-1, j ] → b[1...j-1 ] + b[j]。

所以， f[i][j] = f[i-1][j-1] + 1。

（2）若a[i]≠b[j]，且a[i]不在公共子序列中，则可以去掉a[i]。

a[1...i-1, i ] → a[1...i-1 ] ；

b[1...j-1, j ] → b[1...j-1, j ] 。

所以， f[i][j] = f[i-1][j]。

（3）若a[i]≠b[j]，且b[i]不在公共子序列中，则可以去掉b[i]。

a[1...i-1, i ] → a[1...i-1, i ] ；

b[1...j-1, j ] → b[1...j-1 ] 。

 

 所以， f[i][j] = f[i][j-1]。

【数据结构】

        为算法上的需要，定义两个字符数组，用于存储两个字符串，一个二维数组，用于求解最长公共子序列。

（1）a[i]：存储字符串。
（2）b[j]：存储字符串。
（3）f[i][j]：表示前缀子串a[1...i]与b[1...j]的“最长公共子序列”的长度。

【动规分析】 

算法思想：请参见：

https://www.bilibili.com/video/BV14A411v7mP?from=search&seid=2293598163041195354&spm_id_from=333.337.0.0

（1）划分阶段。

        阶段：已经处理的前缀长度（两个字符串中的位置，即一个二维坐标）。

（2）确定状态和状态变量。

        状态：f 数组表示前缀子串 a[1...i] 与 b[1...j] 的“最长公共子序列”的长度。

（2）确定决策并写出状态转移方程。

        f[i][j]的值从哪来？当a[i]=b[j]时，从f[i-1][j-1]而来，当a[i]≠b[j]时，从f[i-1][j] 或 f[i][j-1]而来。策略：最长公共子串，故，状态转移方程：

        。

（4）寻找边界条件。

         边界：f[i][0] = f[0][j] = 0，目标：f[n][m]。

（5）设计并实现程序，数据存储和问题求解过程如下：

NULL和任何字符串都没有公共子序列，任何字符串和NULL也都没有公共子序列。

如果a[i]=a[j]，f[i][j]=f[i-1][j-1]+1

如果a[i]≠a[j]，f[i][j]=max(f[i][j-1], f[i-1][j])

 【参考代码】

#include <stdio.h>
#include <string.h>
#define MAXN 1010
 
int f[MAXN][MAXN];
char s[MAXN],t[MAXN];
 
int max(int x,int y)
{
	return x > y ? x : y;
}
int main()
{
	int i,j;
	int len_s,len_t;
	scanf(" %s %s",s,t);
	
	len_s=strlen(s);
	len_t=strlen(t);
	
	for(i=1;i<=len_s;i++)
	{
		for(j=1;j<=len_t;j++)
		{
			if(s[i-1]==t[j-1])
				f[i][j]=f[i-1][j-1]+1;
			else
				f[i][j]=max(f[i-1][j],f[i][j-1]);
		}
	}
	printf("%d\n",f[len_s][len_t]);
	return 0;
}

信息学奥赛一本通（C++版）在线评测系统