DP在字符匹配上的实现

在此保存下近段时间做的DP在字符匹配上的实现的题目

对于不同的字符串来说，2者只能不断将下标往后推移来实现匹配从而得到的最大匹配数

如 abcd 和 dcba 这个最大匹配数只能为1，因为两个d匹配后，在第一个字符串中是不能再拿前面的字符进行匹配的（当然你要是匹配a，b，c也是一样的道理）

对于每一道题目若想不断找到那个匹配成功的字符的话，我们需要一个函数不断递归找到前一个匹配成功的字符，这里引进一个T[N][N]的标志位来帮助我们判断何时进行递归

这里的题都是有关这个的形式

1.POJ 1458http://vjudge.net/problem/viewProblem.action?id=17083

这就是最基本的2个字符串的最大匹配数

dp[i][j]代表前一个字符串取i位，后一个字符串取j位时得到的最大匹配数

DP 方程：dp[i][j]={dp[i-1][j-1]+1,a[i]==b[j] | max(dp[i-1][j],dp[i][j-1])}

自己一开始在做题时写成了dp[i][j]={dp[i-1][j-1]+1,a[i]==b[j] | max(dp[i][j],dp[i-1][j-1])}

这样仔细想想很容易发现dp[i][j]=max(dp[i][j],dp[i-1][j-1]) 只是考虑了一部分的状态，而且本身在i，j2次循环时dp[i][j]也只出现了一次，也就是说只

进行了一次赋值操作，根本就不会进行更新操作

dp[i][j]=max(dp[i-1][j],dp[i][j-1])却可以在循环中不断将前面得到的最大值赋给后面；

for(int j=1;j<=lb;j++)
                if(a[i-1]==b[j-1])
                {
                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
                }
                else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);//这一段要注意，这是为了匹配到2段数组均在小于它的情况下所得
        }
总代码如下：

#include <cstdio>

#include <cstring>

using namespace std;

#define N 1001

#define max(a,b) a>b?a:b;

int dp[N][N];

char a[N],b[N];

int main()

{

    while(scanf("%s%s",a,b)!=EOF){

        memset(dp,,sizeof(dp));

        int la=strlen(a),lb=strlen(b);

        for(int i=;i<=la;i++){

            for(int j=;j<=lb;j++)

                if(a[i-]==b[j-])

                {

                    dp[i][j]=max(dp[i][j],dp[i-][j-]+);

                }

                else dp[i][j]=max(dp[i][j-],dp[i-][j]);//这一段要注意，这是为了匹配到2段数组均在小于它的情况下所得

        }

        printf("%d\n",dp[la][lb]);

    }

    return ;

}

但是我们想要不断找到那个匹配成功的字符的话，我们需要一个函数不断递归找到前一个匹配成功的字符，这里引进一个T[N][N]的标志位来帮助我们判断何时进行递归

这是递归函数

 void output(int len1,int len2)

 {

     if(len1==||len2==) return;

     if(T[len1][len2]==){

         output(len1-,len2-);

         printf("%c\n",a[len1-]);

     }

     else if(T[len1][len2]==) output(len1-,len2);

     else output(len1,len2-);

 }

这是T[][]在进行寻找最长子序列时进行赋值

在第二题中要用到这个方法，就不再详述

2.POJ 2250

http://vjudge.net/problem/viewProblem.action?id=17325

这与上面不同的是这是给2堆字符串，找其中尽可能多的相同的字符串并输出

这里需要用到output（int，int）进行递归调用

总代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <string>

 using namespace std;

 #define N 103

 string a[N],b[N];

 int dp[N][N],T[N][N],len1,len2,cnt=;

 void match(int len1,int len2)

 {

     memset(dp,,sizeof(dp));

     for(int i=;i<=len1;i++)

     {

         for(int j=;j<=len2;j++)

         {

             if(a[i-]==b[j-]) dp[i][j]=dp[i-][j-]+,T[i][j]=;

             else{

                 if(dp[i-][j]>dp[i][j-]) dp[i][j]=dp[i-][j],T[i][j]=;

                 else dp[i][j]=dp[i][j-],T[i][j]=;

             }

         }

     }

 }

 void output(int m,int n)

 {

     if(m==||n==) return;

     if(T[m][n]==){

         output(m-,n-);

         cnt++;

         if(cnt==dp[len1][len2])

             cout<<a[m-]<<endl;

         else cout<<a[m-]<<' ';

     }

     else if(T[m][n]==) output(m-,n);

     else output(m,n-);

 }

 int main()

 {

     string str;

     while(cin>>str)

     {

         len1=,len2=;

         a[]=str;

         while(cin>>str&&str.at()!='#'){

             a[len1++]=str;

         }

         while(cin>>str&&str.at()!='#'){

             b[len2++]=str;

         }

         match(len1,len2);

         output(len1,len2);

         //cout<<dp[len1][len2]<<endl;

     }

     return ;

 }

巴特西

DP在字符匹配上的实现

最新文章

热门文章