【25.10.28】模拟赛

T1

code

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,M=1e3+5;
int n,m,ans=0;
char s[N],t[M];
int nxt[M];
int f[N][M];
int g[M][30];
void getnxt(){nxt[1]=0;int j=0;for(int i=2;i<=m;++i){while(j>0&&t[i]!=t[j+1])  j=nxt[j];if(t[i]==t[j+1])  ++j;nxt[i]=j;}
}
void getval(){for(int i=0;i<m;++i){for(int c=0;c<26;++c){int j=i;while(j>0&&c!=t[j+1]-'a')  j=nxt[j];if(c==t[j+1]-'a')  ++j;g[i][c]=j;
//			cout<<i<<" "<<c<<" "<<g[i][c]<<endl;}}
}
//int calc(int pos,char c){
//	int j=pos;
//	while(j>0&&c!=t[j+1])  j=nxt[j];
//	if(c==t[j+1])  ++j;
//	cout<<pos<<" "<<c<<" "<<j<<endl;
//	return j;
//}
int main(){freopen("neck.in","r",stdin);freopen("neck.out","w",stdout);cin>>s+1;cin>>t+1;n=strlen(s+1);m=strlen(t+1);getnxt();getval();for(int i=0;i<n;++i)for(int j=0;j<m;++j){int val=g[j][s[i+1]-'a'];f[i+1][j]=max(f[i+1][j],f[i][j]);if(val==m)  continue;f[i+1][val]=max(f[i+1][val],f[i][j]+1);}for(int i=0;i<m;++i)ans=max(ans,f[n][i]);printf("%d\n",ans);fclose(stdin);fclose(stdout);return 0;
}