首页 > 代码库 > DP在字符匹配上的实现
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,0,sizeof(dp)); int la=strlen(a),lb=strlen(b); for(int i=1;i<=la;i++){ 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段数组均在小于它的情况下所得 } printf("%d\n",dp[la][lb]); } return 0;}
但是我们想要不断找到那个匹配成功的字符的话，我们需要一个函数不断递归找到前一个匹配成功的字符，这里引进一个T[N][N]的标志位来帮助我们判断何时进行递归
这是递归函数
1 void output(int len1,int len2) 2 { 3 if(len1==0||len2==0) return; 4 if(T[len1][len2]==1){ 5 output(len1-1,len2-1); 6 printf("%c\n",a[len1-1]); 7 } 8 else if(T[len1][len2]==2) output(len1-1,len2); 9 else output(len1,len2-1);10 }
这是T[][]在进行寻找最长子序列时进行赋值
在第二题中要用到这个方法，就不再详述
2.POJ 2250
http://vjudge.net/problem/viewProblem.action?id=17325
这与上面不同的是这是给2堆字符串，找其中尽可能多的相同的字符串并输出
这里需要用到output（int，int）进行递归调用
总代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 using namespace std; 6 #define N 103 7 string a[N],b[N]; 8 int dp[N][N],T[N][N],len1,len2,cnt=0; 9 10 void match(int len1,int len2)11 {12 memset(dp,0,sizeof(dp));13 for(int i=1;i<=len1;i++)14 {15 for(int j=1;j<=len2;j++)16 {17 if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1,T[i][j]=1;18 else{19 if(dp[i-1][j]>dp[i][j-1]) dp[i][j]=dp[i-1][j],T[i][j]=2;20 else dp[i][j]=dp[i][j-1],T[i][j]=3;21 }22 }23 }24 }25 void output(int m,int n)26 {27 if(m==0||n==0) return;28 if(T[m][n]==1){29 output(m-1,n-1);30 cnt++;31 if(cnt==dp[len1][len2])32 cout<<a[m-1]<<endl;33 else cout<<a[m-1]<<‘ ‘;34 }35 else if(T[m][n]==2) output(m-1,n);36 else output(m,n-1);37 }38 int main()39 {40 string str;41 while(cin>>str)42 {43 len1=1,len2=0;44 a[0]=str;45 while(cin>>str&&str.at(0)!=‘#‘){46 a[len1++]=str;47 }48 while(cin>>str&&str.at(0)!=‘#‘){49 b[len2++]=str;50 }51 match(len1,len2);52 output(len1,len2);53 //cout<<dp[len1][len2]<<endl;54 }55 return 0;56 }