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