本文共 755 字，大约阅读时间需要 2 分钟。

题目大意

给出一段长串s1和它的一段非连续子串s2，求s1最长的连续删除区间，使得s2仍为s1的非连续子串

题解

最大分割情况只可能是两种，一种是最左端或者最右端删去一大段，另一种是中间任意两个字母间删去一大段

①先看第一种，那么肯定是要找到s2在s1中的最左相同点和最右相同点，很简单

②另一种，删去的区间端点两个字母肯定是s2中相邻的字母，即保证删去中间一段没用的，仍是子串 例如s1:abbccbbbcccddde s2: ab

#include
   
    using namespace std;const int maxn=2e5+5;char s[maxn],t[maxn];int pre[maxn],bac[maxn];int main(){
       scanf("%s",s);    scanf("%s",t);    int lens=strlen(s);    int lent=strlen(t);    int j=0;    for(int i=0;i
    
     
      =0&&j>=0;i--){
           if(s[i]==t[j])            bac[j--]=i;    }    int kmax=max(max(pre[0],lens-1-pre[lent-1]),max(bac[0],lens-1-bac[lent-1]));//第一种情况    for(int i=1;i
     
    
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/100106762 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！