某山寨

z4zr的待调教小窝

POJ1458 Common Subsequence DP 最长公共子序列

Tag:C/C++ dp lcs poj acm

POJ1458 Common Subsequence DP 最长公共子序列

POJ1458
题目大意:
输入2个字符串 输出两个字符串最长公共子序列。。
eg:
input: abcfbc abfcab (注意!这条数据 字串的顺序可能变了。。。)
programming contest
abcd mnp
output:4
2
0

p.s. 原题没有给出字符串的长度。。。。经测试300可以过去。。。

先声明一下,最长公共子串和最长公共子序列(lcs)是不同的 度娘也容易犯错误。。。常常找到无关的东西。。
字串是连续的。。。 子序列是不连续的但是是顺序的。。

Thisisz4zr'sspace 中
z4zr是字串 iz4spc是子序列

题目的意思明确和简单,对于没有震惊学习过的我来说 额 没思路啊有木有 最笨的模拟方法必然超时到下个世纪。。
首先创建一个二位数组dp305 稍微开大一点 如果不是为了最小内存最短代码+最短时间什么的 代码还是不要苛刻的去优化。。
首先先来判断一种一一对应的最长子串:
input: z4zrlovesnow z4zrisz4zrlogo
output:6
连续对应的位置相同的
如果用n,m表示两个字符串的长度的话,那么算法的时间复杂度为O(nm),空间复杂度也为O(nm)
首先初始化dp数组全部为0,让第一串字符串为str,第二串字符串为sub
然后每遇到str[i]==sub[j] dpi=dpi-1+1 既对应位置加一。。
str[i]!=sub[j] dpi=0
这样 看看dp数组会变成什么样子:

  z 4 z r i s z 4 z r l o g o
z 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 1 0 1 0 0 0 1 0 1 0 0 0 0
z 0 0 2 0 0 0 0 0 2 0 0 0 0 0
r 0 1 0 3 0 0 0 1 0 3 0 0 0 0
l 0 0 0 0 4 0 0 0 0 0 4 0 0 0
o 0 0 0 0 0 0 0 0 0 0 0 5 0 0
v 0 0 0 0 0 0 0 0 0 0 0 0 6 0
e 0 0 0 0 0 0 0 0 0 0 0 0 0 0
s 0 0 0 0 0 0 0 0 0 0 0 0 0 0
n 0 0 0 0 0 0 1 0 0 0 0 0 0 0
o 0 0 0 0 0 0 0 0 0 0 0 0 0 0
w 0 0 0 0 0 0 0 0 0 0 0 0 1 0

对应的位置就是 比较的位置 额 也就是说这里面最大的数字 就是最长的共同字串
对应的解决程序如下,实现了找到最长的完全相同的字串的长度:

#include<stdio.h>
#include<string.h>
int dp[102][102];
char str[101],sub[101];
int main(){
    int i,j,l_str,l_sub,max_ans;
    while(scanf("%s%s",str,sub)!=EOF){
        memset(dp,0,sizeof(dp));
        max_ans=0;
        l_str=strlen(str);
        l_sub=strlen(sub);
        for(i=0;i<l_str;i++){
            for(j=0;j<l_sub;j++){
                if(str[i]==sub[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                    if(max_ans<dp[i+1][j+1])
                        max_ans=dp[i+1][j+1];
                }
                else dp[i+1][j+1]==0;
            }
        }
        printf("%d\n",max_ans);
    }
    return 0;
}

好了我们似乎已经可以得到最长的字串了。。但是这里只有这样是不够的
题目的第一组数据已经告诉我们这样是不够的。。。
该解决题目中的问题了。。最长公共子序列 需要记忆之前匹配的内容
所以修改一下规则:
str[i]==sub[j] dpi=dpi-1+1
str[i]!=sub[j] <span style="text-decoration: underline">dpi=max(dpi-1,dpi);</span>
下划线的部分 算是状态转移方程,这个东西一定要自己能写出来。。
当然刚开始都是些不出来了,。。。千万别总是找模版 模版这东西虽然方便 但是会让人产生依赖 大神与我们的区别就在于 大神敲的解题代码都被我们拿来当模版了
对应的上面三组数据 看一下dp数组里面数据的样子 去理解可能会好一点

abcfbc         abfcab
  a b c f b c
a 1 1 1 1 1 2
b 1 2 2 2 2 3
f 1 2 2 3 3 4
c 1 2 3 3 3 4
a 1 2 3 3 3 4
b 1 2 3 3 4 4
ans: 4
programming    contest
  p r o g r a m m i n g
c 0 0 0 0 0 0 0 0 0 0 0
o 0 0 1 1 1 1 1 1 1 1 1
n 0 0 1 1 1 1 1 1 1 2 2
t 0 0 1 1 1 1 1 1 1 2 2
e 0 0 1 1 1 1 1 1 1 2 2
s 0 0 1 1 1 1 1 1 1 2 2
t 0 0 1 1 1 1 1 1 1 2 2
ans: 2

代码:

//744K  0MS G++ 701B
#include<stdio.h>
#include<string.h>
int dp[302][302];
char str[301],sub[301];
int maxn(int a,int b){
    return a>b?a:b;
}
int main(){
    int i,j,l_str,l_sub,max_ans;
    while(scanf("%s%s",str,sub)!=EOF){
        memset(dp,0,sizeof(dp));
        max_ans=0;
        l_str=strlen(str);
        l_sub=strlen(sub);
        for(i=0;i<l_str;i++){
            for(j=0;j<l_sub;j++){
                if(str[i]==sub[j]){
                    dp[i+1][j+1]=dp[i][j]+1;
                }
                else {
                    dp[i+1][j+1]=maxn(dp[i][j+1],dp[i+1][j]);//状态转移方程
                }
            }
        }
        printf("%d\n",dp[l_str][l_sub]);
    }
    return 0;
}

附:空间复杂度O(2*n)的代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int dp[2][5010];
char s1[5010];
char s2[5010];
int n,m;
void solve()
{
    int i,j;
    int k1,k2;
    memset(dp,0,sizeof(dp));
    n=strlen(s1);
    m=strlen(s2);
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            k1=i%2;
            k2=(i+1)%2;
            if(s1[i-1]==s2[j-1])
            {
                dp[k1][j]=dp[k2][j-1]+1;
            }
            else
                dp[k1][j]=max(dp[k2][j],dp[k1][j-1]);
        }
    }
    printf("%d\n",dp[n%2][m]);
}
int main()
{
    for(; scanf("%s %s",s1,s2)!=EOF;)
    {
        solve();
    }
    return 1;
}

添加新评论

文章二维码