時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 177 解決: 92
題目描述
我們稱序列Z=<z1,z2,...,zk>是序列X=<x1,x2,...,xm>的子序列當(dāng)且僅當(dāng)存在嚴(yán)格上升的序列<i1,i2,...,ik>，使得對j=1,2,...,k,有xij=zj。比如Z=<a,b,f,c> 是X=<a,b,c,f,b,c>的子序列。
現(xiàn)在給出兩個(gè)序列X和Y，你的任務(wù)是找到X和Y的最大公共子序列，也就是說要找到一個(gè)最長的序列Z，使得Z既是X的子序列也是Y的子序列。
輸入格式
輸入包括多組測試數(shù)據(jù)。每組數(shù)據(jù)包括一行，給出兩個(gè)長度不超過200的字符串，表示兩個(gè)序列。兩個(gè)字符串之間由若干個(gè)空格隔開。
輸出格式
對每組輸入數(shù)據(jù)，輸出一行，給出兩個(gè)序列的最大公共子序列的長度。
樣例輸入
abcfbc abfcab
programming contest
abcd mnp
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情
標(biāo)簽