2011-10-02 09:16:51Morris
a252. Another LCS
a252. Another LCS
/**********************************************************************************/
/* Problem: a252 "Another LCS" from 成功高中校內賽初賽 第三題 */
/* Language: C (577 Bytes) */
/* Result: AC(2ms, 1.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-02 07:13:26 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int Max(int x, int y) {
return x > y ? x : y;
}
int main() {
char s1[101], s2[101], s3[101];
char DP[101][101][101], i, j, k;
while(scanf("%s %s %s", s1, s2, s3) == 3) {
memset(DP, 0, sizeof(DP));
for(i = 0; s1[i]; i++)
for(j = 0; s2[j]; j++)
for(k = 0; s3[k]; k++) {
if(s1[i] == s2[j] && s2[j] == s3[k])
DP[i+1][j+1][k+1] = DP[i][j][k] + 1;
else
DP[i+1][j+1][k+1] = Max(Max(DP[i+1][j+1][k], DP[i+1][j][k+1]), DP[i][j+1][k+1]);
}
printf("%d\n", DP[i][j][k]);
}
return 0;
}
內容 :
一般LCS問題( Longest Common subsequence, 最長共同子字串)就是給定兩個字串,求出他們的LCS。為了理解這裡子字串定義,舉例來說,對於字串
abccdda
abc、adda、aca、bda等都是它的子字串,但adc、bdde、bddd等不是他的子字串。
對於兩個字串accbbeffg、fcebg,他們的LCS長度為 3,而LCS為cbg或ceg。
現在我們把問題弄得難一點,給三個字串,請求出他們的LCS長度為多少?
輸入說明
:
每個測資檔僅包含一筆測資,每筆測資有三個字串。測資保證三個字串的長度都不超過100,而且字串皆由小寫字母組成。
輸出說明
:
對每筆測資,輸出LCS的長度。
範例輸入 :
abe acb babcd
範例輸出 :
2
提示
:
背景知識:
DP
出處
:
/**********************************************************************************/
/* Problem: a252 "Another LCS" from 成功高中校內賽初賽 第三題 */
/* Language: C (577 Bytes) */
/* Result: AC(2ms, 1.2MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-02 07:13:26 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
int Max(int x, int y) {
return x > y ? x : y;
}
int main() {
char s1[101], s2[101], s3[101];
char DP[101][101][101], i, j, k;
while(scanf("%s %s %s", s1, s2, s3) == 3) {
memset(DP, 0, sizeof(DP));
for(i = 0; s1[i]; i++)
for(j = 0; s2[j]; j++)
for(k = 0; s3[k]; k++) {
if(s1[i] == s2[j] && s2[j] == s3[k])
DP[i+1][j+1][k+1] = DP[i][j][k] + 1;
else
DP[i+1][j+1][k+1] = Max(Max(DP[i+1][j+1][k], DP[i+1][j][k+1]), DP[i][j+1][k+1]);
}
printf("%d\n", DP[i][j][k]);
}
return 0;
}
上一篇:a251. 假費波那契數
下一篇:a253. 王老先生的磨菇田