t是s的子序列的意思是：从s中删去若干个字符，可以得到t；特别的，如果s=t,那么t也是s的子序列；空串是任何串的子序列。例如:"acd"是“abcde”的子序列，“acd"是“acd”的子序列，但"adc” 不是“abcde”的子序列。

s[x..y]表示s[x] ...s[y]共y-x+l个字符构成的字符串，若x>y则 s[x..y]是空串。t[x..y]同理。

#include <iostream>


#include <string>


using namespace std;


const int max1 = 202;


string s, t;


int pre[max1], suf[max1];





int main() {


    cin >> s >> t;


    int slen = s.length(), tlen = t.length();





    for (int i = 0, j = 0; i < slen; ++i) {


        if (j < tlen && s[i] == t[j]) ++j;


        pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列


    }





    for (int  i = slen - 1 , j = tlen - 1; i >= 0; --i) {


        if(j >= 0 && s[i] == t [j]) --j;


        suf[i]= j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列


    }





    suf[slen] = tlen -1;


    int ans = 0;


    for (int i = 0, j = 0, tmp = 0; i <= slen; ++i){


        while(j <= slen && tmp >= suf[j] + 1) ++j;


        ans = max(ans, j - i - 1);


        tmp = pre[i];


    }


    cout << ans << endl;


    return 0;


}

提示： t[0..pre[i] -1]是 s[0..i]的子序列；

t[suf[i]+1..tlen-1]是 s[i..slen-1]的子序列。

判断题

选择题