Codeforces Round #579 (Div. 3) D2. Remove the Substring (hard version) (思维,贪心)

题意:给你一个模式串\(t\),现在要在主串\(s\)中删除多个子串,使得得到的\(s\)的子序列依然包含\(t\),问能删除的最长子串长度.
题解:首先,我们不难想到,我们可以选择\(s\)头部到最右边的子序列的头部和最左边的子序列的尾部到\(s\)的尾部这两个子串,除去这两个子串,我们要找的最大子串一定在子序列的头部到尾部中,即子序列中两个相邻字符位置的间隔,那么很显然,我们想让相邻的字符之间相隔最大,所以问题也就转化成了:求模式串的相邻字符在主串中的最大间隔长度,最优的情况一定是最左的子序列到最右的子序列的间隔最大,我们可以正着反着记录模式串中每个字符第一次出现的位置,然后求差更新答案即可.

代码:

string s;

string t;

int pre[N];

int suf[N];

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>s>>t;

	int lens=(int)s.size();

	int lent=(int)t.size();

	int j=0;

	rep(i,0,lens){

		if(s[i]==t[j] && j<lent){

			pre[j++]=i;

		}

	}

	j=lent-1;

	per(i,lens-1,0){

		if(s[i]==t[j] && j>=0){

			suf[j--]=i;

		}

	}

	int ans=suf[0];

	rep(i,0,lent-2){

		ans=max(ans,suf[i+1]-pre[i]-1);

	}

	ans=max(ans,lens-1-pre[lent-1]);

	cout<<ans<<'\n';

    return 0;

}

巴特西

Codeforces Round #579 (Div. 3) D2. Remove the Substring (hard version) (思维,贪心)

最新文章

热门文章