Submission #1005521

---

Source Code Expand

#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

const int INF=5e8;
int n;
string s,t;

pi ps[1000005];

void ng(){
  puts("-1");
  exit(0);
}

int main(){
  cin>>n>>s>>t;
  if(s==t){
    puts("0");
    return 0;
  }

  int q=n-1;
  int m=0;
  for(int i=n-1;i>=0;--i){
    int j=i;
    while(j>=0 && t[j]==t[i]) --j;

    int p=i;
    q=min(j+1,q);
    while(q>=0 && s[q]!=t[p]) --q;

    if(q<0) ng();

    ps[m++]=mp(q,p);
    if(p<q) ng();

    i=j+1;
  }
  ps[m++]=mp(INF,0);
  sort(ps,ps+m);

  int lb=-1,ub=n+1;
  while(ub-lb>1){
    int md=(lb+ub)>>1;
    bool fail=false;
    REP(i,m-1){
      int trg=ps[min(m-1,i+md)].fr-md;
      if(trg<ps[i].sc) fail=true;
    }
    if(fail) lb=md;
    else ub=md;
  }
  printf("%d\n",ub);
  return 0;
}

Submission Info

Judge Result