第 30 题 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]的子序列。
判断题
第 30 题 （1分）程序输出时，suf数组满足：对任意0 <= i < slen, suf[i] < suf[i + 1]。 （）
第 31 题 （2分）当t是s的子序列时，输出一定不为0。（）
第 32 题 （2分）程序运行到第23行时，“j - i - 1” 一定不小于0。（）
第 33 题 （2分）当t是s的子序列时，pre数组和suf数组满足：对任意0 <= i < slen, pre[i] > suf[i + 1] + 1。 （）
第 34 题 若tlen=10,输出为0,则slen最小为（）。
第 35 题 若tlen=10,输出为2,则slen最小为（）。