codeforces 1203D2 思路

文章目录[x]
  1. 1:链接
  2. 2:题意
  3. 3:思路
  4. 4:参考代码

csdn博客链接:https://blog.csdn.net/nuoyanli/article/details/105108013


链接

https://codeforces.com/problemset/problem/1203/D2

题意

有一个字符串,以及中的一个子序列,现在要求你将删去最长一段字串,删去之后还是的子序列,求删去的最长字串有多长。

思路

只三种情况,删去的是的前缀、后缀、中间一段。处理也很容易,尽量在前面找出来,尽量在后面找出来,并且记录找出的中每一个字符对应在中的位置,这个时候删去前缀后缀就直接解决了问题。中间一段就枚举从前面找个字符,后面找个字符,因为之前已经处理了相对的位置,减一下,中间就出来了。

详细见代码

参考代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define PB push_back
#define FI first
#define SE second
#define m_p(a, b) make_pair(a, b)
const double pi = acos(-1.0);
const double eps = 1e-9;
typedef long long LL;
const int N = 1e6 + 10;
const int M = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double f = 2.32349;
char s[N], t[N];
int lens, lent, pre[N], suf[N];
// lens为s的长度,lent为t的长度,pre记录t在s尽量前端找出来的时候相对每个字母位置,suf为后段
int pre_m() { //尽量在s前段找出t来
  int ls = 0, lt = 0, cnt = 0;
  for (int i = 0; i < lens; i++) {
    if (s[ls] == t[lt]) {
      lt++;
      pre[++cnt] = ls;
    }
    ls++;
    if (lt == lent)
      break;
  }

  return lens - ls;
}

int tail_m() { //尽量在s后段找出t来
  int rs = lens - 1, rt = lent - 1, cnt = 0;
  for (int i = lens - 1; i >= 0; i--) {
    if (s[rs] == t[rt]) {
      suf[++cnt] = rs;
      rt--;
    }
    rs--;
    if (rt == -1)
      break;
  }

  return rs + 1;
}
void solve() {
  IOS;
  cin >> s >> t;
  lens = strlen(s);
  lent = strlen(t);
  int ans = 0;
  ans = max(ans, pre_m());
  ans = max(ans, tail_m());
  for (int i = 1; i <= lent; i++) {
    //删去中间一段,就用前面和后面找出来的位置拼起来
    ans = max(ans, suf[lent - i] - pre[i] - 1);
  }
  cout << ans << endl;
}
signed main() {
  solve();
  return 0;
}

 


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像