822E - Liar - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;
const int N=5e5+5,K=35,mod=1e9+7;
void chkmax(int &x,int y){x=max(x,y);}
void chkmin(int &x,int y){x=min(x,y);}
void Add(int &x,int y){x+=y,x%=mod;}
int ab(int x){if(x<0)x=-x;return x;}

int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+(ch-'0'),ch=getchar();
	return x*f;
}

struct str{
	int sum[N],rk[N],sa[N],lrk[N*2],height[N],id[N],n;
	int st[N][20];
	char s[N];
	int cmp(int x,int y,int k){
		return (lrk[x]==lrk[y])&&(lrk[x+k]==lrk[y+k]);
	}
	int query(int l,int r){
		int k=log2(r-l+1);
		return min(st[l][k],st[r-(1<<k)+1][k]);
	} 
	int lcp(int x,int y){
		int l=rk[x],r=rk[y];
	  if(l>r)swap(l,r);
	  return query(l+1,r);
	}
	void build_height(){
		int k=0;
		for(int i=1;i<=n;i++){
			if(k)k--;
			while(s[i+k]==s[sa[rk[i]-1]+k])k++;
			height[rk[i]]=k;
		}
		for(int i=1;i<=n;i++)st[i][0]=height[i];
		for(int k=1;k<=19;k++){
			for(int i=1;i+(1<<k)-1<=n;i++)st[i][k]=min(st[i][k-1],st[i+(1<<(k-1))][k-1]);
		}
	}
	void SA(){
	  int cnt=128;
	  for(int i=0;i<=cnt;i++)sum[i]=0;
	  for(int i=1;i<=n;i++)sum[rk[i]=s[i]]++;
	  for(int i=1;i<=cnt;i++)sum[i]+=sum[i-1];
	  for(int i=n;i>=1;i--)sa[sum[rk[i]]--]=i;	
	  for(int k=1;k<=n;k*=2){
		  cnt=0;
		  for(int i=n;i>n-k;i--)id[++cnt]=i;
		  for(int i=1;i<=n;i++)if(sa[i]>k)id[++cnt]=sa[i]-k;
		  for(int i=0;i<=n;i++)sum[i]=0;
		  for(int i=1;i<=n;i++)sum[lrk[i]=rk[i]]++;
		  for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
		  for(int i=n;i>=1;i--)sa[sum[rk[id[i]]]--]=id[i];
		  cnt=0;
		  for(int i=1;i<=n;i++)if(cmp(sa[i-1],sa[i],k))rk[sa[i]]=rk[sa[i-1]];else rk[sa[i]]=++cnt;
		  if(cnt==n)break;
	  }
		build_height();
	}
}S; 

char s[N],t[N];
int dp[N][K],n,m,k;

int main(){
	n=read(),scanf("%s",s+1),m=read(),scanf("%s",t+1),k=read();
	for(int i=1;i<=n;i++)S.s[i]=s[i];
	S.s[n+1]='#',S.n=n+m+1;
	for(int i=1;i<=m;i++)S.s[i+n+1]=t[i];
	S.SA();
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			chkmax(dp[i][j],dp[i-1][j]);
			int L=S.lcp(i,dp[i-1][j]+1+n+1);
			if(L)chkmax(dp[i+L-1][j+1],dp[i-1][j]+L);
		}
		for(int j=0;j<=k;j++){
			if(dp[i][j]==m)printf("YES\n"),exit(0);
		}
	}
  printf("NO\n");
	return 0;
}