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

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

1#include <iostream>2#include <string>3using namespace std;4const int max1 = 202;5string s, t;6int pre[max1], suf[max1];7 8int main() {9    cin >> s >> t;10    int slen = s.length(), tlen = t.length();11 12    for (int i = 0, j = 0; i < slen; ++i) {13        if (j < tlen && s[i] == t[j]) ++j;14        pre[i] = j; // t[0..j-1] 是 s[0..i] 的子序列15    }16 17    for (int  i = slen - 1 , j = tlen - 1; i >= 0; --i) {18        if(j >= 0 && s[i] == t [j]) --j;19        suf[i]= j; // t[j+1..tlen-1] 是 s[i..slen-1] 的子序列20    }21 22    suf[slen] = tlen -1;23    int ans = 0;24    for (int i = 0, j = 0, tmp = 0; i <= slen; ++i){25        while(j <= slen && tmp >= suf[j] + 1) ++j;26        ans = max(ans, j - i - 1);27        tmp = pre[i];28    }29    cout << ans << endl;30    return 0;31}

提示：

• $t[0\dots pre[i]-1]$ 是 $s[0\dots i]$ 的子序列；
• $t[suf[i]+1\dots tlen-1]$ 是 $s[i\dots slen-1]$ 的子序列。