|
|
| |
|
最长公共子序列
|
||||
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列=<  >，则另一序列Z＝ 是x的子序列是指存在一个严格递增的下标序列 ,使得对于所有j＝1，2,…，k有 ,例如，序列Z＝<B，C，D，B>是序列x＝<A，B，C，B，D，A，B)的子序列，相应的递增下标序列为<2，3，5，7>。给定两个序列x和y，当另一序列Z既是x的子序列又是y的子序列时，称Z是序列x,y的公共子序列。例如，若x=<A，B，C，B，D，A，B>和y＝<B，D，C，A，B，A>，则序列<B，C，A>是x和y的一个公共子序列，序列＜B，C，B，A＞也是x和y的一个公 共子序列。而且，后者是x和y的一个最长公共子序列，因为x和y没有长度大于4的公共子序列。 设有n 个由字符和数字组成的长度不等的序列 
。当序列S 是序列
，i=1~n,的子序列时，称序列S 为序列
的一个公共子序列。编程任务：对于给定的n 个序列
编程计算其最长公共子序列的长度。约束条件：n≤10000,字符串长度均不超过255。 数据输入：由文件INPUT3.* 提供输入数据，文件共有n 行，每行给出一个序列。最后以一空行结束。文件名由键盘输入。 |
||||
| 网站导航
| 关于曙光 | 联系我们
| 请提意见 Copyright © FuJian Sunshine Educational Info. Co.,Ltd. 福建曙光教育资讯有限公司 版权所有 |