L 给出一个s和t 求s一个最长子串使得s中不存在t中长度大于2的子串。
直接的想法是状压dp 不过复杂度很高。仔细考虑当前形成子串中若包含t的一个字符所形成的的限制是 该字符后的一些字符无法使用。
那么维护包含最靠前的字符可以把之前的限制包含。同时选这个字符时还需要考虑这个字符最后出现的位置也要比当前字符限制靠前。
限制数为26个 状态数可以接受。
code
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#define rep(a,b,k) for(int k=a;k<=b;++k)
using namespace std;
//设 f{i,j} 表示 到了i 里面有t字符的靠前位置为j的最大长度
const int MAXN=500010;
int n,m,cnt,cnt2;
char t[MAXN],s[MAXN];
int pos[MAXN];
int a[MAXN],b[MAXN],c[MAXN],w[MAXN],vis[MAXN],last[MAXN];
int f[30];
int main()
{
//freopen("1.in","r",stdin);
scanf("%s",s+1);
scanf("%s",t+1);
n=strlen(s+1);
m=strlen(t+1);
rep(1,n,i){a[i]=s[i]-'a';}
rep(1,m,i)
{
b[i]=t[i]-'a';
if(pos[b[i]]){vis[b[i]]=1;}
if(!pos[b[i]])pos[b[i]]=i,c[++cnt]=i,w[i]=cnt;
last[b[i]]=i;
}
rep(1,n,i)
{
int w1=pos[a[i]];
if(!w1){++cnt2;continue;}
if(!vis[a[i]])++f[w[w1]];
//if(i==n)cout<<w[w1]<<' '<<"ww"<<endl;
rep(w[w1]+1,cnt,j)
{
if(last[a[i]]<c[j])
f[w[w1]]=max(f[w[w1]],f[j]+1);
}
f[w[w1]]=max(f[w[w1]],1);
//cout<<f[1]<<endl;
}
int ww=0;
rep(1,cnt,i)ww=max(ww,f[i]);
printf("%d\n",ww+cnt2);
return 0;
}