{"id":348,"date":"2012-05-17T14:42:47","date_gmt":"2012-05-17T06:42:47","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=348"},"modified":"2020-06-06T14:43:36","modified_gmt":"2020-06-06T06:43:36","slug":"%e6%9c%80%e9%95%bf%e5%85%ac%e5%85%b1%e5%ad%90%e5%ba%8f%e5%88%97","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=348","title":{"rendered":"\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>\/\/\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\n \n\/\/\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u5730\u5f52\u89e3\u6cd5\npackage wkx;\n \nimport java.io.IOException;\n \npublic class Test { \n\t\n\tprivate static int LCSLength(char&#91;] A, char&#91;] B, int&#91;]&#91;] m, int&#91;]&#91;] s,\n\t\t\tint i, int j) {\n\t\tif (i &lt; 0 || j &lt; 0)\n\t\t\treturn 0;\n\t\tif (m&#91;i]&#91;j] != 0)\n\t\t\treturn m&#91;i]&#91;j];\n\t\tif (A&#91;i] == B&#91;j]) {\n\t\t\ts&#91;i]&#91;j] = 1;\n\t\t\tm&#91;i]&#91;j] = LCSLength(A, B, m, s, i - 1, j - 1) + 1;\n\t\t} else {\n\t\t\tint a = LCSLength(A, B, m, s, i - 1, j);\n\t\t\tint b = LCSLength(A, B, m, s, i, j - 1);\n\t\t\tif (a > b) {\n\t\t\t\ts&#91;i]&#91;j] = 2;\n\t\t\t\tm&#91;i]&#91;j] = a;\n\t\t\t} else {\n\t\t\t\ts&#91;i]&#91;j] = 3;\n\t\t\t\tm&#91;i]&#91;j] = b;\n\t\t\t}\n\t\t}\n\t\treturn m&#91;i]&#91;j];\n\t}\n \n\tprivate static void LCS(char&#91;] A, int&#91;]&#91;] s, int i, int j,StringBuffer str) {\n\t\tif (i &lt; 0 || j &lt; 0)\n\t\t\treturn;\n\t\tif (s&#91;i]&#91;j] == 1) {\n\t\t\tstr.append(A&#91;i]);\n\t\t\tLCS(A, s, i - 1, j - 1,str);\n\t\t} else if (s&#91;i]&#91;j] == 2) {\n\t\t\tLCS(A, s, i - 1, j,str);\n\t\t} else {\n\t\t\tLCS(A, s, i, j - 1,str);\n\t\t}\n\t}\n \n\tpublic static void main(String&#91;] args) throws IOException {\n\t\tString A = \"ASSBDGCGDHDERDFGG\";\n\t\tString B = \"ASBSSCDEF\";\n\t\tif (A.length() &lt; B.length()) {\n\t\t\tString t = A;\n\t\t\tA = B;\n\t\t\tB = t;\n\t\t}\n\t\tint&#91;]&#91;] m = new int&#91;100]&#91;100];\n\t\tint&#91;]&#91;] s = new int&#91;100]&#91;100];\n\t\tSystem.out.println(\"Total : \"\n\t\t\t\t+ LCSLength(A.toCharArray(), B.toCharArray(), m, s,\n\t\t\t\t\t\tA.length() - 1, B.length() - 1));\n\t\tStringBuffer str=new StringBuffer();\n\t\tLCS(A.toCharArray(), s, A.length() - 1, B.length() - 1,str);\n\t\tSystem.out.println(str.reverse());\n\t}\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-348","post","type-post","status-publish","format-standard","hentry","category-06-03-play-ground"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/348","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=348"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/348\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=348"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=348"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=348"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}