2090 問題 C: 藍橋杯算法提高VIP-最長字符序列
時間限制: 1s
內(nèi)存限制: 128MB 提交: 380 解決: 0
題目描述
設(shè)x(i), y(i), z(i)表示單個字符，則X={x(1)x(2)……x(m)}，Y={y(1)y(2)……y(n)}，Z={z(1)z(2)……z(k)},我們稱其為字符序列，其中m,n和k分別是字符序列X，Y，Z的長度，括號()中的數(shù)字被稱作字符序列的下標(biāo)。
如果存在一個嚴(yán)格遞增而且長度大于0的下標(biāo)序列{i1,i2……ik}，使得對所有的j=1,2,……k，有x(ij)=z(j)，那么我們稱Z是X的字符子序列。而且，如果Z既是X的字符子序列又是Y的字符子序列，那么我們稱Z為X和Y的公共字符序列。
在我們今天的問題中，我們希望計算兩個給定字符序列X和Y的最大長度的公共字符序列，這里我們只要求輸出這個最大長度公共子序列對應(yīng)的長度值。
舉例來說，字符序列X=abcd，Y=acde，那么它們的最大長度為3，相應(yīng)的公共字符序列為acd。
輸入
輸入一行，用空格隔開的兩個字符串
輸入字符串長度最長為100，區(qū)分大小寫。
輸出
輸出這兩個字符序列對應(yīng)的最大長度公共字符序列的長度值
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點擊這里了解課程詳情