2010年7月11日 星期日

Problem 10405 Longest Common Subsequence,最長共同子字串

建議大家可以上網去找「最長共同子字串」的演算法,此演算法是由「最長連續共同子字串」推演而來。「最長共同子字串」的方法就是依序比對字串,將最佳比對結果逐一往陣列右下方推,推到最後,答案就出來了。
C 語言程式碼如下:
#define LEN 1000

char seq1[LEN + 1], seq2[LEN + 1];

int lcs_length(int s1Len, int s2Len)
{
int i, j;
int table[s1Len + 1][s2Len + 1];
memset(table, 0, sizeof(table));

for(i = 1; i <= s1Len; ++i) {
for(j = 1; j <= s2Len; ++j) {
if(seq1[i - 1] == seq2[j - 1])
table[i][j] = table[i - 1][j - 1] + 1;
else if(table[i - 1][j] > table[i][j - 1])
table[i][j] = table[i - 1][j];
else
table[i][j] = table[i][j - 1];
}
}
return table[s1Len][s2Len];
}

int main()
{

while (gets(seq1))
{
gets(seq2);
int s1Len = strlen(seq1), s2Len = strlen(seq2);
printf("%d\n", lcs_length(s1Len, s2Len));
}

return 0;
}

By David.K

p10405題目連結
回ACM題庫目錄
回首頁

沒有留言: