比赛 CSP2023-J模拟赛 评测结果 ATAAAAATAAAAAAAATATA
题目名称 切分子串 最终得分 80
用户昵称 hcy 运行时间 4.000 s
代码语言 C++ 内存使用 1.15 MiB
提交时间 2023-10-18 18:49:32
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
string s,t;
int b[2500]={0},a[200]={0};
int m,n;
int q=0,h=0;
void dfs1(int x,int y){
	q=max(q,y-1);
	if(x>m||y>n||q==n){
		return;
	}
	if(b[x]==a[y]){
		dfs1(x+1,y+1);
	}
	dfs1(x+1,1);
	return;
}
void dfs2(int x,int y){
	h=max(h,n-y);
	if(x==0||y==0||h==n){
		return;
	}
	if(b[x]==a[y]){
		dfs2(x-1,y-1);
	}
	dfs2(x-1,n);
	return;
}
int main(){
	freopen("cutstring.in","r",stdin);
	freopen("cutstring.out","w",stdout);
	cin>>s;
	m=s.length();
	for(int i=1;i<=m;i++){
		b[i]=s[i-1]-'a'+1;
	}
	cin>>t;
	n=t.length();
	for(int i=1;i<=n;i++){
		a[i]=t[i-1]-'a'+1;
	}
	dfs1(1,1);
	dfs2(m,n);
	h=n-h+1;
	if(q<h){
		return 0;
	}
	else if(q==n&&h==1){
		cout<<q-h<<endl;
		return 0;
	}
	else if(q==n||h==1){
		cout<<q-h+1<<endl;
		return 0;
	}
	cout<<q-h+2<<endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}