四、阅读程序-3

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]的子序列。

信息学奥赛历年真题

Quiz Summary

Information

Results

Results

Categories

1. Question

2. Question

3. Question

4. Question

5. Question

6. Question