Submission #40743659

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=1e6+10,INF=1e9;
void tomin(int& x,int y){x=min(x,y);}
void tomax(int& x,int y){x=max(x,y);}

int n;
char s[MAXN],t[MAXN];

int pre[26],R[MAXN],cnt;


void ERR(int x){
	cout<<x;
	exit(0);
}

typedef array<int,2> itv;

itv a[MAXN];

int main(){

	cin>>n>>(s+1)>>(t+1);

	int p=n;
	per(i,n,1){
		if(p>i)p=i;
		while(p>=1 && s[p] != t[i])p--;
		if(!p)ERR(-1);

		tomax(R[p],i);
	}

	rep(i,1,n)if(R[i] > i)a[++cnt]={i,R[i]};

	int ans=0;

	rep(l,1,cnt){
		int L=l+1,R=cnt,res=l;
		while(L<=R){
			int mid=(L+R)>>1;
			if(a[mid][0] - (mid-l-1) <= a[l][1]){
				res=mid;L=mid+1;
			}else{
				R=mid-1;
			}
		}
		tomax(ans,res-l+1);
	}

	cout<<ans<<endl;

    return 0;
}

Submission Info

Judge Result