点击打开链接
题目意思: 给定两个字符串求出最长公共子序列(注意和最长公共字串相区别)
解题思路: 动态规划(节省空间可以加上滚动数组)
根据最长公共子序列问题的性质,我们可以规定dp[i][j]为字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度, 由于下面涉及到i-1和j-1,那么这个时候我们一般从i=1和j=1开始到i<=len1, j<=len2。
1 ch1[i-1] = ch2[j-1] ,那么dp[i][j]= dp[i-1][j-1] + 1;
2 ch1[i-1] != ch2[j-1] ,那么我们知道ch1[i]和ch2[j]不可能在同一个公共子序列里出现,那么这个时候的最长的子序列可能以ch1[i]或ch2[j]结尾,那么由于dp[i][j]= max {dp[i-1][j] , dp[i][j-1]};
这个时候所有i=0或j=0的dp[i][j]= 0;
0 ; i = 0或j= 0;
就有 dp = dp[i][j] = dp[i-1][j-1] + 1; i > 0且j> 0 且ch1[i-1]= ch2[j-1];
dp[i][j]= max {dp[i-1][j] , dp[i][j-1]};i > 0且j> 0且ch1[i-1]!= ch2[j-1];
代码:有滚动数组
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 30010
char ch1[MAXN] , ch2[MAXN];
int dp[2][MAXN];//这里是压缩第一维,因为后面的for循环中j是一直变化的
int longest;
void solve(){
int i , j;
int len1 = strlen(ch1);
int len2 = strlen(ch2);
memset(dp , 0 , sizeof(dp)) ; longest = 0;
for(i = 1 ; i <= len1 ; i++){
for(j = 1 ; j <= len2 ; j++){
if(ch1[i-1] == ch2[j-1]) dp[i%2][j] = dp[(i-1)%2][j-1]+1;
else dp[i%2][j] = dp[(i-1)%2][j]>dp[i%2][j-1]?dp[(i-1)%2][j]:dp[i%2][j-1];
if(dp[i%2][j] > longest) longest = dp[i%2][j];
}
}
printf("%d\n" , longest);
}
int main(){
//freopen("input.txt" , "r" , stdin);
while(gets(ch1)){
gets(ch2) ; solve();
}
return 0;
}
没用滚动数组
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 1010
char ch1[MAXN] , ch2[MAXN];
int dp[MAXN][MAXN];
int longest;
void solve(){
int i , j;
int len1 = strlen(ch1);
int len2 = strlen(ch2);
memset(dp , 0 , sizeof(dp)) ; longest = 0;
for(i = 1 ; i <= len1 ; i++){
for(j = 1 ; j <= len2 ; j++){
if(ch1[i-1] == ch2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
if(dp[i][j] > longest) longest = dp[i][j];
}
}
printf("%d\n" , longest);
}
int main(){
//freopen("input.txt" , "r" , stdin);
while(gets(ch1)){
gets(ch2) ; solve();
}
return 0;
}
分享到:
相关推荐
前端工程师面试
前端工程师面试
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
北大POJ2533-Longest Ordered Subsequence 解题报告+AC代码
这是动态规划中,求最长公共子序列(Longest common string)的源代码。自己编写执行。程序简单,有注释。
北大POJ2533-Longest Ordered Subsequence【O(n^2)】
关于Longest Common Subsequences演算法
Longest Common Ancestor classic ppt...
最长公共子序列演示程序,算法分析与设计,动态规划算法
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
LeetCode Longest Common Prefix解决方案
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
最长公共子序列Longest Common Subsequence - Super Jiju的小窝_ To be with my Dearest Jessie
最长公共子序列问题,动态规划法
Longest Common Extension with RecompressionTomohiro I Kyushu Institute of Technology, Japantomohiro@ai.kyutech.ac.jpAbstractGiven two positions i and j in a string T of length N , a longest common ...
C#,最长公共扩展(LCE,Longest Common Extention)的算法与源代码 考虑一个字符串s,并为每对(L,R)计算从L和R开始的s的最长子字符串。 在LCE中,在每个查询中,我们必须回答从索引L和R开始的最长公共前缀的长度...
自述文件该自述文件通常会记录启动和运行应用程序所需的所有步骤。 您可能要讲的内容: Ruby版本系统依赖配置数据库创建数据库初始化如何运行测试套件服务(作业队列,缓存服务器,搜索引擎等) 部署说明...