Submission #38256951

---

Source Code Expand

#include<bits/stdc++.h>
#define N 200009
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,ch[N][27],head[50];
char s[N],t[N];
inline ll rd(){
	ll x=0;char c=getchar();bool f=0;
	while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f?-x:x;
}
bool check(int mid){
	int g=0,p=0;
	for(int i=mid+1;i<=n;++i){
		p=ch[p][s[i]-'a'];
		if(p==n+1){
			g=1;
			break;
		}
	}
	if(!g)return 1;
	return 0;
}
int pp[50];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>(s+1)>>(t+1);
	for(int i=1;i<=n;++i){
		pp[s[i]-'a']++;
		pp[t[i]-'a']--;
	}
	int g=0;
	for(int i=0;i<26;++i){
		if(pp[i]!=0){
			g=1;
		}
	}
	if(g){
		cout<<-1<<endl;
		return 0;
	}
	for(int i=0;i<26;++i)head[i]=n+1;
	for(int i=n;i>=0;--i){
		for(int j=0;j<26;++j){
			ch[i][j]=head[j];
		}
		if(i)head[t[i]-'a']=i;
	}
	int l=0,r=n,ans=n;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	cout<<ans;
    return 0;
}

Submission Info

Judge Result