紧急求助!求助站外题!
  • 板块学术版
  • 楼主卷王慢即快
  • 当前回复10
  • 已保存回复10
  • 发布时间2022/8/9 16:26
  • 上次更新2023/10/27 16:16:42
查看原帖
紧急求助!求助站外题!
494699
卷王慢即快楼主2022/8/9 16:26

本萌新有一题不会,求教!

#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[0pre[i]1]t[0\dots pre[i]-1]s[0i]s[0\dots i] 的子序列;

  • t[suf[i]+1tlen1]t[suf[i]+1\dots tlen-1]s[islen1]s[i\dots slen-1] 的子序列。


其实整个程序我好像都没搞懂,希望大佬能帮帮忙。(我总是感觉第一个帮助我的是AlgorithmerSnow)

我不会的问题:

  • 判断题:

    1. ttss 的子序列时,输出一定不为 00。(正确答案:×)

    2. ttss 的子序列时,pre 数组和 suf 数组满足:对任意 0i<slen,pre[i]>suf[i+1]+10 \leq i < slen, pre[i] > suf[i + 1] + 1。 (正确答案:√)

  • 选择题:

    1. tlen=10tlen=10,输出为 00,则 slenslen 最小为()。(正确答案:D)

    A. 1010

    B. 1212

    C. 00

    D. 11

    1. tlen=10tlen=10,输出为 22,则 slenslen 最小为()。(正确答案:C)

    A. 00

    B. 1010

    C. 1212

    D. 11


本蒟蒻太菜了,程序的意思都没搞懂,求大佬指教!

2022/8/9 16:26
加载中...