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