2602 問題 D: 藍(lán)橋杯2020年第十一屆國賽真題-藍(lán)肽子序列
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 933 解決: 256
題目描述
L 星球上的生物由蛋藍(lán)質(zhì)組成,每一種蛋藍(lán)質(zhì)由一類稱為藍(lán)肽的物資首尾連接成一條長鏈后折疊而成。
生物學(xué)家小喬正在研究 L 星球上的蛋藍(lán)質(zhì)。她拿到兩個(gè)蛋藍(lán)質(zhì)的藍(lán)肽序列,想通過這兩條藍(lán)肽序列的共同特點(diǎn)來分析兩種蛋藍(lán)質(zhì)的相似性。
具體的,一個(gè)藍(lán)肽可以使用 1 至 5 個(gè)英文字母表示,其中第一個(gè)字母大寫,后面的字母小寫。一個(gè)蛋藍(lán)質(zhì)的藍(lán)肽序列可以用藍(lán)肽的表示順序拼接而成。
在一條藍(lán)肽序列中,如果選取其中的一些位置,把這些位置的藍(lán)肽取出,并按照它們?cè)谠蛄兄械奈恢脭[放,則稱為這條藍(lán)肽的一個(gè)子序列。藍(lán)肽的子序列不一定在原序列中是連續(xù)的,中間可能間隔著一些未被取出的藍(lán)肽。
如果第一條藍(lán)肽序列可以取出一個(gè)子序列與第二條藍(lán)肽序列中取出的某個(gè)子序列相等,則稱為一個(gè)公共藍(lán)肽子序列。
給定兩條藍(lán)肽序列,找出他們最長的那個(gè)公共藍(lán)肽子序列的長度。
輸入
輸入兩行,每行包含一個(gè)字符串,表示一個(gè)藍(lán)肽序列。字符串中間沒有空格等分隔字符。
輸出
輸出一個(gè)整數(shù),表示最長的那個(gè)公共藍(lán)肽子序列的長度。
樣例輸入
LanQiaoBei
LanTaiXiaoQiao
提示
【樣例說明】
最長的公共藍(lán)肽子序列為 LanQiao,共兩個(gè)藍(lán)肽。
【評(píng)測(cè)用例規(guī)模與約定】
對(duì)于 20% 的評(píng)測(cè)用例,兩個(gè)字符串的長度均不超過 20。
對(duì)于 50% 的評(píng)測(cè)用例,兩個(gè)字符串的長度均不超過 100。
對(duì)于所有評(píng)測(cè)用例,兩個(gè)字符串的長度均不超過 1000。