算法分析与设计-第07章.pptVIP

7.4.3最长公共子序列算法【例7-6】设有两个序列X=(x1,x2,…,x7)=(a,b,c,b,d,a,b),Y=(y1,y2,…,y6)=(b,d,c,a,b,a),求最长公共子序列。为了能够构造最长公共子序列，在求c[i][j]的同时，还求s[i][j]。上格≥左格上格左格S[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1，c[i-1][j]和c[i][j-1]中的哪一个计算得到的。这一信息将用于构造最长公共子序列。0000000000000000c[i][j]0111s[i][j]由于a?b,且上格?左格,故取上格000000000000002同时置为2221由于a=a，故取左上格+1同时置为1314最后c[7][6]=4即为最长公共子序列的长度由于a?b,且上格左格,故取左格同时置为3s[i][j]abcb即LCS为：(x2,x3,x4,x6)=(b,c,b,a)LCS的构造【程序7-5】求LCS的长度classLCS{public:LCS(intnx,intny,char*x,char*y);voidLCSLength();voidCLCS();……private:voidCLCS(inti,intj);int**c,**s,m,n;char*a,*b;};intLCS::LCSLength(){for(inti=1;i=m;i++)c[i][0]=0;//0列置0for(i=1;i=n;i++)c[0][i]=0;//0行置0for(i=1;i=m;i++)for(intj=1;j=n;j++)if(x[i]==y[j])//xi=yj时{c[i][j]=c[i-1][j-1]+1;s[i][j]=1;}//左上格+1elseif(c[i-1][j]=c[i][j-1])//上格≥左格{c[i][j]=c[i-1][j];s[i][j]=2;}//则取上格else{c[i][j]=c[i][j-1];s[i][j]=3;}//否则取左格returnc[m][n];}//时间复杂度为O(m?n)【程序7-6】构造最长公共子序列voidLCS::CLCS(inti,intj){if(i==0||j==0)return;if(s[i][j]==1){CLCS(i-1,j-1);//往左上格走couta[i];}elseif(s[i][j]==2)CLCS(i-1,j);//往上格走elseCLCS(i,j-1);//往左格走}O(m+n)7.4.4算法的改进改进方法一：由于c[i][j]是由c[i][j]=c[i-1][j-1]+1(s[i][j]=1),c[i][j]=c[i-1][j](s[i][j]=2)或c[i][j]=c[i][j-1](s[i][j]=3)得到，从它就可以判断c[i][j]是从三者中哪一个计算得到的，而不必借助s，从而达到节省存储空间的目的。这样改进后的时间是O(m+n)。4abcb即LCS为：(x2,x3,x4,x6)=(b,c,b,a)从右下角出发c[i][j]改进方法一由于b≠a,且上格?下格，故往上走。由于a=a,故往左上格走。由于c≠a,且上格左格，故往左走。改进方法二：在只求最长公共子序列的长度、无需构造最优解时，也可以只用两行元素空间，时间是O(min{m,n})。原因：计算c[i][j]时仅用到第i行和第i-1行元素。c[0][n]c[1][n]c[2][n]改进方法二01