“`” \u53c2\u8003\u56de\u7b54\uff1a<\/p>\n
\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u4ee3\u7801<\/p>\n
<pre><code>void LCS(string X, string Y, vector & a)
\n{
\nint m=X.length(),n=Y.length();
\nfor (int j = 1; j <= n; j++) {
\na[0]=0;\/\/\u5185\u5c42\u5faa\u73af\u7ed3\u675f,a[0]\u8981\u7f6e\u96f6\uff0c\u60f3\u8c61\u6c42a1\u6240\u4f9d\u8d56\u7684a0=0\uff0c\u5373\u662f\u521d\u59cb\u5316\u6b65\u9aa4
\n for (int i = 1; i <= m; i++) {
\n int pre=a[0];
\n int temp = a[i];
\n if (X[i – 1] == Y[j – 1])
\n a[i] =pre+1;
\n else a[i] = max(a[i],a[i-1]);
\n a[0]=temp;
\n }
\n }
\n }
\n\/\/ci\u8868\u793aX\u7684\u524di\u4e2a\u5b57\u7b26\u548cY\u7684\u524dj\u4e2a\u5b57\u7b26\u6240\u5171\u6709\u7684\u5e8f\u5217\u957f\u5ea6\uff1bbi\u7528\u6765\u56de\u6eaf\u5f97\u5230\u7684\u516c\u5171\u5b50\u5e8f\u5217<\/p>\n
void LCS_LENGTH(string X,string Y,vector> & b,vector> & c)
\n {
\n int m=X.length(),n=Y.length();
\n for(int i=0;i<=m;i++)
\n c[i][0]=0;
\n for(int j=0;j<=n;j++)
\n c[0][j]=0;
\n int i,j;
\n for(i=1;i<=m;i++)
\n for(j=1;j<=n;j++)
\n if(X[i-1]==Y[j-1])
\n {
\n c[i][j]=c[i-1][j-1]+1;
\n b[i][j]=2;
\n }else if(c[i-1][j]>=c[i][j-1])
\n {
\n c[i][j]=c[i-1][j];
\n b[i][j]=1;
\n }else
\n {
\n c[i][j]=c[i][j-1];
\n b[i][j]=0;
\n }
\n }
\n \/\/\u5229\u7528\u56de\u6eaf\u548c\u8868b,\u8ffd\u8e2aLCS<\/p>\n
void PRINT_LCS(vector> & b, string X,int xlen, int ylen,string &s)
\n {
\n int i=xlen,j=ylen;
\n if(i==0||j==0)
\n return ;
\n if(bi==2)\/\/\u6b64\u65f6\u7b2ci\u4e2a\u5143\u7d20Xi-1\u5c5e\u4e8e\u516c\u5171\u5143\u7d20
\n {
\n PRINT_LCS(b,X,i-1,j-1,s);
\n s+=X[i-1];
\n }
\n else if(bi==1)\/\/\u4e0a\u9762\u6709ci=ci-1;\u6b64\u65f6\u56de\u6eafci-1
\n PRINT_LCS(b,X,i-1,j,s);
\n }
\n else
\n PRINT_LCS(b,X,i,j-1,s);
\n}<\/p>\n
<\/code><\/pre><\/p>\n
\u00a0<\/p>\n
<pre><code> "“`
\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
“`” \u53c2\u8003\u56de\u7b54\uff1a \u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u4ee3\u7801 <pre><code> […]<\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[101],"tags":[],"class_list":["post-45262","post","type-post","status-publish","format-standard","hentry","category-c"],"_links":{"self":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45262","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/comments?post=45262"}],"version-history":[{"count":1,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45262\/revisions"}],"predecessor-version":[{"id":45263,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/posts\/45262\/revisions\/45263"}],"wp:attachment":[{"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/media?parent=45262"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/categories?post=45262"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/wx.kaifamiao.info\/index.php\/wp-json\/wp\/v2\/tags?post=45262"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}