nyoj--36--最长公共子序列

灰太狼 2022-05-26 06:25 119阅读 0赞

## 最长公共子序列 ##

时间限制： 3000 ms  |  内存限制： 65535 KB

难度： 3

描述

咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列。  
tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

输入

第一行给出一个整数N(0<N<100)表示待测数据组数 
接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000.

输出

每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。

样例输入

2
    asdf
    adfsd
    123abc
    abc123abc

样例输出

3
    6

思路：

动态规划思想，

如果str1\[m\]==str2\[n\]的情况下,长度应该是：len\[m-1\]\[n-1\]+1;

如果str1\[m\]!=str2\[n\]的情况下，长度应该是：max(len\[m\]\[n-1\],len\[m-1\]\[n\]);

Java Code

<table style="width:100%;font-family:Consolas, 'Courier New';font-size:12px;vertical-align:text-top;line-height:15px;"> 
 <tbody> 
 <tr> 
 <td style="color:#008284;background-color:#e3e3e3;vertical-align:text-top;"> 
 <div style="margin:7px;text-align:right;white-space:nowrap;">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 
 </div></td> 
 <td style="background-color:#008284;padding:1px;"> 
 <div style="border:1px #008284 solid;"></div></td> 
 <td style="background-color:#efefef;width:100%;vertical-align:text-top;color:#000000;"> 
 <div style="margin:7px;">
 #include&nbsp;&lt;bits/stdc++.h&gt; 
 using&nbsp;namespace&nbsp;std; 
 
 int 
 &nbsp;main() { &nbsp;&nbsp;&nbsp;&nbsp; 
 int 
 &nbsp;N,i,j; &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d" 
 ,&amp;N); &nbsp;&nbsp;&nbsp;&nbsp; 
 while 
 (N--) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 char 
 &nbsp;str1[ 
 1005 
 ],str2[ 
 1005 
 ]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%s%s" 
 ,str1,str2); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int 
 &nbsp;len1=strlen(str1),len2=strlen(str2); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int 
 &nbsp;LCS[len1+ 
 1 
 ][len2+ 
 1 
 ]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(LCS, 
 0 
 ,sizeof(LCS)); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 (i= 
 1 
 ;&nbsp;i&lt;=len1;&nbsp;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 (j= 
 1 
 ;&nbsp;j&lt;=len2;&nbsp;j++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if 
 (str1[i- 
 1 
 ]==str2[j- 
 1 
 ]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LCS[i][j]=LCS[i- 
 1 
 ][j- 
 1 
 ]+ 
 1 
 ; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;LCS[i][j]=max(LCS[i- 
 1 
 ][j],LCS[i][j- 
 1 
 ]); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n" 
 ,LCS[len1][len2]); &nbsp;&nbsp;&nbsp;&nbsp;} } 
 </div></td> 
 </tr> 
 </tbody> 
</table>