求助ABC F WA*1
  • 板块灌水区
  • 楼主lfxxx_
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/29 21:32
  • 上次更新2024/12/30 18:28:27
查看原帖
求助ABC F WA*1
795344
lfxxx_楼主2024/12/29 21:32
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=5e5+5,delta=55;
string s,t;
int K,n,m;
int dp[N][110];
ull h[2][N],pw[N];
ull query(ull *ha,int l,int r){return ha[r]-ha[l-1]*pw[r-l+1];}
int lcp(int x,int y)
{
    int l=1,r=min(n-x,m-y)+1,ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(query(h[0],x,x+mid-1)==query(h[1],y,y+mid-1))
            ans=mid,l=mid+1;
        else
            r=mid-1;
    }
    return x+ans;
}
signed main()
{
	cin>>K>>s>>t;
	n=s.size(),m=t.size();
	if(abs(n-m)>K)
		cout<<"No",exit(0);
	s="#"+s,t="#"+t;
	pw[0]=1;
	for(int i=1;i<=N-1;++i)
		pw[i]=pw[i-1]*131;
	for(int i=1;i<=n;++i)
		h[0][i]=h[0][i-1]*131+s[i];
	for(int i=1;i<=m;++i)
		h[1][i]=h[1][i-1]*131+t[i];
	if(lcp(1,1)>n&&lcp(1,1)>m)
		cout<<"Yes",exit(0);
	dp[0][delta]=lcp(1,1);
	for(int i=1;i<=K;++i)
	{
		for(int j=-K;j<=K;++j)
		{
			int st=max(max(dp[i-1][j+delta+1],dp[i-1][j+delta])+1,dp[i-1][j+delta-1]);
			if(j+st>=0)
				dp[i][j+delta]=lcp(st,j+st);
		}
		if(m-n+delta>=0&&dp[i][m-n+delta]>n)
			cout<<"Yes",exit(0);
	}
	cout<<"No";
} 
2024/12/29 21:32
加载中...