本萌新有一题不会,求教!
#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] 的子序列。
其实整个程序我好像都没搞懂,希望大佬能帮帮忙。(我总是感觉第一个帮助我的是AlgorithmerSnow)
我不会的问题:
判断题:
当 t 是 s 的子序列时,输出一定不为 0。(正确答案:×)
当 t 是 s 的子序列时,pre 数组和 suf 数组满足:对任意 0≤i<slen,pre[i]>suf[i+1]+1。 (正确答案:√)
选择题:
A. 10
B. 12
C. 0
D. 1
A. 0
B. 10
C. 12
D. 1
本蒟蒻太菜了,程序的意思都没搞懂,求大佬指教!