/* * * * * * * * * * * ID: Haidara * * LANG: C++17 * * PROB: * * * * * * * * * * */ #include<bits/stdc++.h> #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define rep(i,x,n) for(int i=x;i<n;i++) #define FOR(i,n) rep(i,0,n) #define per(i,x,n) for(int i=x;i>n;i--) #define ROF(i,x) for(int i=x;i>=0;i--) #define v(i) vector< i > #define p(i,j) pair< i , j > #define pii pair<int,int> #define m(i,j) map< i , j > #define pq(i) priority_queue< i > #define ff first #define all(x) x.begin(),x.end() #define ss second #define pp push_back using namespace std; const int mod=1e9+7; const int maxn=100100; int st[3][2][maxn*4]; string str[2]; int sz; int idx; void build(int l=1,int r=sz,int inx=1) { if(l==r) { if(str[idx][l]=='T') st[2][idx][inx]=1; if(str[idx][l]=='C') st[2][idx][inx]=1; if(str[idx][l]=='A') st[2][idx][inx]=1; return ; } int mid=l+(r-l)/2; build(l,mid,inx*2); build(mid+1,r,inx*2+1); FOR(i,3) st[i][idx][inx]=st[i][idx][inx*2]+st[i][idx][inx*2+1]; return ; } int f[3],s[3]; void query(int ql,int qr,int l=1,int r=sz,int inx=1) { if(ql<=l&&r<=qr) { FOR(i,3) f[i]+=st[i][0][inx],s[i]+=st[i][1][inx]; return ; } if(l>qr||r<ql) return ; int mid=l+(r-l)/2; query(ql,qr,l,mid,inx*2); query(ql,qr,mid+1,r,inx*2+1); return ; } void init(string a, string b) { str[0]=a; str[1]=b; sz=max(a.size(),b.size()); } int get_distance(int x, int y) { x++,y++; FOR(i,3) f[i]=s[i]=0; int ans=y-x; query(x,y); FOR(i,3) if(f[i]!=s[i]) ans=-1; return ans; }