- 浏览: 32679 次
最新评论
如果两种特征序列的公共子序列越长表示越接近,现在请你帮助计算出最长的公共特征。
输入说明:
本问题有多组测试数据,第一行就是测试数据的组数(1<=组数<=20)。对于每一组测试数据,有两行,每一行都是有大写英文字母组成的特征序列(1<=特征序列的长度<=1000)。
输出说明:
对于每一组输入,对应的输出只有一行,即最长的公共子序列的长度。
Sample Input:
1
ABDCRHGWDWSDSKJDSKDFHJKFDKJDSAFKJFDAKFDSAJFDKASDJLFLDKF
ERUDSHDFHGFLKGFGFKGFLKSAEWALUTRHGFKIFDGITRMDFLKDSLSDLLEHJFKLEKIREFMFK
Sample Output:
25
#include<iostream>
#include<string>
using namespace std;
#define MAX 1001
int nZ[MAX][MAX];
void vInit(int nA,int nB);
void vGetLcs(string sA,string sB);
int nMax(int nA,int nB);
void vOut(int nA,int nB);
int main()
{
int i;
int nCase;
string sX,sY;
int nX,nY;
cin>>nCase;
for(i=1;i<=nCase;i++)
{
cin>>sX>>sY;
sX=" "+sX;
sY=" "+sY;
nX=sX.size()-1;
nY=sY.size()-1;
vInit(nX,nY);
vGetLcs(sX,sY);
vOut(nX,nY);
}
return 0;
}
void vInit(int nA,int nB)
{
int i,j;
for(j=1;j<=nB;j++)
{
nZ[0][j]=0;
}
for(i=1;i<=nA;i++)
{
nZ[i][0]=0;
}
}
void vGetLcs(string sA,string sB)
{
int i,j;
int nA,nB;
nA=sA.size()-1;
nB=sB.size()-1;
for(i=1;i<=nA;i++)
{
for(j=1;j<=nB;j++)
{
if(sA[i]==sB[j])
{
nZ[i][j]=nZ[i-1][j-1]+1;
}
else
{
nZ[i][j]=nMax(nZ[i][j-1],nZ[i-1][j]);
}
}
}
}
int nMax(int nA,int nB)
{
return(nA>nB?nA:nB);
}
void vOut(int nA,int nB)
{
cout<<nZ[nA][nB]<<endl;
}
输入说明:
本问题有多组测试数据,第一行就是测试数据的组数(1<=组数<=20)。对于每一组测试数据,有两行,每一行都是有大写英文字母组成的特征序列(1<=特征序列的长度<=1000)。
输出说明:
对于每一组输入,对应的输出只有一行,即最长的公共子序列的长度。
Sample Input:
1
ABDCRHGWDWSDSKJDSKDFHJKFDKJDSAFKJFDAKFDSAJFDKASDJLFLDKF
ERUDSHDFHGFLKGFGFKGFLKSAEWALUTRHGFKIFDGITRMDFLKDSLSDLLEHJFKLEKIREFMFK
Sample Output:
25
#include<iostream>
#include<string>
using namespace std;
#define MAX 1001
int nZ[MAX][MAX];
void vInit(int nA,int nB);
void vGetLcs(string sA,string sB);
int nMax(int nA,int nB);
void vOut(int nA,int nB);
int main()
{
int i;
int nCase;
string sX,sY;
int nX,nY;
cin>>nCase;
for(i=1;i<=nCase;i++)
{
cin>>sX>>sY;
sX=" "+sX;
sY=" "+sY;
nX=sX.size()-1;
nY=sY.size()-1;
vInit(nX,nY);
vGetLcs(sX,sY);
vOut(nX,nY);
}
return 0;
}
void vInit(int nA,int nB)
{
int i,j;
for(j=1;j<=nB;j++)
{
nZ[0][j]=0;
}
for(i=1;i<=nA;i++)
{
nZ[i][0]=0;
}
}
void vGetLcs(string sA,string sB)
{
int i,j;
int nA,nB;
nA=sA.size()-1;
nB=sB.size()-1;
for(i=1;i<=nA;i++)
{
for(j=1;j<=nB;j++)
{
if(sA[i]==sB[j])
{
nZ[i][j]=nZ[i-1][j-1]+1;
}
else
{
nZ[i][j]=nMax(nZ[i][j-1],nZ[i-1][j]);
}
}
}
}
int nMax(int nA,int nB)
{
return(nA>nB?nA:nB);
}
void vOut(int nA,int nB)
{
cout<<nZ[nA][nB]<<endl;
}
发表评论
-
最大子段和
2012-01-05 13:59 779给出N个数字, 计算出最大的子段和。 Input 第一行给 ... -
最长不下降子序列长度
2012-01-05 13:55 1308对于序列(1, 7, 3, 5, 9, 4,,有它的一些不下降 ... -
编辑距离问题
2012-01-05 13:48 658#include<iostream> #incl ... -
Kruskal最小生成树
2011-12-08 14:26 699#include<iostream> #inclu ... -
prime
2011-12-01 20:09 612#include<iostream> using ... -
哈弗曼编码
2011-11-28 10:43 1#include<iostream> #defi ... -
哈弗曼编码
2011-11-28 10:42 520#include<iostream> #defi ... -
#贪心算法(零件加工)
2011-10-27 13:25 981#include<stdio.h> #includ ... -
众数问题
2011-10-20 14:57 789#include <stdio.h> #inclu ... -
输油管道问题
2011-10-13 14:45 598#include <stdio.h> #inclu ... -
幂的精确求值
2011-09-22 15:07 461#include<iostream> using ... -
大数加法
2011-09-22 12:56 606#include<iostream> #incl ... -
三姐妹之出题
2011-09-15 14:15 663#include<iostream> #incl ... -
最大子段和问题(分治)(##)
2011-09-08 21:31 665#include<stdio.h> #defin ... -
最大子段和问题(O(N^2))
2011-09-08 15:04 610#include<stdio.h> int a[ ... -
最大子段和问题(O(N^3))
2011-09-08 14:45 476#include<stdio.h> int a[ ...
相关推荐
给定一个字符串和一个字符串字典,找到字典里面最长的字符串,该字符串可以 通过删除给定字符串的某些字符来得到。如果答案不止一个,返回长度最长且字 典顺序最小的字符串。如果答案不存在,则返回空字符串。 示例...
删除字符串中某个字符,找到匹配的最长子序列 LongestWordInDictionary 排序 找出数字数组中的第k个大的位置 ,使用快速选择法 KthElement 在一组数字中,找出出现频率最高的前几位数字 TopKFrequentElements 荷兰...
10.10 最长子序列 204 10.11 最大子串匹配 204 10.12 最大子段和 205 10.13 最大子阵和 206 11.其它 207 11.1 大数(只能处理正数) 207 11.2 分数 212 11.3 矩阵 214 11.4 线性方程组 216 11. 5 线性相关 218 11.6 ...
检查两个字符串数组是否等效-简单 编辑距离-困难 文字对齐-困难 数一数二-轻松 最长子串,不包含重复字符-中 最长的公共前缀-简单 有效数字-硬 用英语重建原始数字-中 删除回文序列-轻松 产生括号-中 检查字符串是否...
这里汇集了浙江大学一些同学的算法,列表如下: 几何\ ... 最长子序列 最大子串匹配 最大子段和 最大子阵和 组合\ 排列组合生成 生成gray码 置换(polya) 字典序全排列 字典序组合 组合公式
10. 最长子序列 120 11. 最大子串匹配 121 12. 最大子段和 122 13. 最大子阵和 123 1.精度计算——大数阶乘 2.精度计算——乘法(大数乘小数) 3.精度计算——乘法(大数乘大数) 4.精度计算——加法 5.精度计算...
几何\ 多边形 多边形切割 浮点函数 几何公式 面积 ... 最长子序列 最大子串匹配 最大子段和 最大子阵和 组合\ 排列组合生成 生成gray码 置换(polya) 字典序全排列 字典序组合 组合公式
无重复字符最长子串 树 验证二叉搜索树 图 拓扑排序 岛屿数量 单词搜索 回溯算法 组合总和 幂集 调度算法 动态规划 最大上升子序列 最小Ascii删除距离 最长回文串 三角形最短路径和 正则表达式匹配 买卖股票问题 ...
ICPC routine library maintained by WishingBone last update on Oct.... 最长子序列 最大子串匹配 最大子段和 最大子阵和 组合\ 排列组合生成 生成gray码 置换(polya) 字典序全排列 字典序组合 组合公式
13.10 最长子序列 125 13.11 最大子串匹配 126 13.12 最大子段和 127 13.13 最大子阵和 127 14、 其它 128 14.1 大数(只能处理正数) 128 14.2 分数 134 14.3 矩阵 136 14.4 线性方程组 138 14.5 线性相关 140 14.6 ...
13.10 最长子序列 125 13.11 最大子串匹配 126 13.12 最大子段和 127 13.13 最大子阵和 127 14、 其它 128 14.1 大数(只能处理正数) 128 14.2 分数 134 14.3 矩阵 136 14.4 线性方程组 138 14.5 线性相关 140 14.6 ...
3 4 升序最长子序列 49 3 5 两位玩家游戏中的必胜策略 52 第 4 章 数组 53 4 1 合并已排序列表 53 4 2 区间的总和 54 4 3 区间内的重复内容 54 4 4 区间的最大总和 55 4 5 查询区间中的最小值:线段树 55 4 6 计算...
一.数论 4 1.阶乘最后非零位 4 2. 模线性方程(组) 4 3. 素数表 6 4. 素数随机判定(miller_rabin) 6 5. 质因数分解 7 ...10. 最长子序列 120 11. 最大子串匹配 121 12. 最大子段和 122 13. 最大子阵和 123
这是我整理过的关于ACM题目常用到的算法代码,word文档,条理清晰,绝对有用。目录如下: 一.数论 1.阶乘最后非零位 2. 模线性方程(组) ...10. 最长子序列 11. 最大子串匹配 12. 最大子段和 13. 最大子阵和
目录 一.数论 4 1.阶乘最后非零位 4 2. 模线性方程(组) 4 3. 素数表 6 4. 素数随机判定(miller_rabin) 6 5. 质因数分解 7 ...10. 最长子序列 120 11. 最大子串匹配 121 12. 最大子段和 122 13. 最大子阵和 123
非常经典的acm程序代码 目录 一.数论 4 1.阶乘最后非零位 4 2. 模线性方程(组) 4 3. 素数表 6 ...4. 素数随机判定(miller_...10. 最长子序列 120 11. 最大子串匹配 121 12. 最大子段和 122 13. 最大子阵和 123
1-longestSubsequence.py:给定一个字符串S,从字典(只是一个列表)D的单词中找出S的最长子序列。 2- student_heights.py:给定一个学生身高的数组,一个一个输入的学生,找到学生可以形成的最小行数,使得任何新...
1 目录 一.数论.... 4 1.阶乘最后非零位 .........2. 模线性方程(组) ........3. 素数表.....10. 最长子序列 ...... 120 11. 最大子串匹配 .. 121 12. 最大子段和 ...... 122 13. 最大子阵和 ...... 123