#include #include #include using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 struct rolling_hash{ long long t_hash; static vector power; static const long long MOD = (1LL<<61)-1; static const long long b = 123456; int sz; rolling_hash(){ sz = 0; t_hash = 0; } rolling_hash(char c){ sz = 1; t_hash = b*c; } long long mul(__int128 x,__int128 y){ __int128 t = x*y; t = (t>>61) + (t&MOD); if(t>=MOD)t -= MOD; return t; } long long get_pow(int sz){ if(power.size()>sz)return power[sz]; while(power.size()<=sz){ if(power.size()==0)power.push_back(1); else power.push_back(mul(power.back(),b)); } return power.back(); } rolling_hash &operator+=(const rolling_hash &another){ (*this).t_hash = mul((*this).t_hash,get_pow(another.sz)); (*this).t_hash += another.t_hash; if((*this).t_hash>=MOD)(*this).t_hash -= MOD; (*this).sz += another.sz; return (*this); } rolling_hash operator+(const rolling_hash &another)const{ return (rolling_hash(*this)+=another); } rolling_hash &operator-=(const rolling_hash &another){ (*this).t_hash += MOD - mul(another.t_hash,get_pow((*this).sz-another.sz)); if((*this).t_hash>=MOD)(*this).t_hash -= MOD; (*this).sz -= another.sz; return (*this); } rolling_hash operator-(const rolling_hash &another)const{ return (rolling_hash(*this)-=another); } bool operator<(const rolling_hash &another)const{ if((*this).t_hash!=another.t_hash)return (*this).t_hash rolling_hash::power; bool check(vector &R,vector &rR,int l,int r){ int n = R.size()-1; return (R[r]-R[l]) == (rR[n-l]-rR[n-r]); } int op(int a,int b){ return min(a,b); } int e(){ return Inf32; } int len; bool f(int x){ return x >= len; } int main(){ string s,t; cin>>s>>t; int n = s.size(); vector R(n+1),rR(n+1); rep(i,n){ R[i+1] = R[i] + rolling_hash(s[i]); } reverse(s.begin(),s.end()); rep(i,n){ rR[i+1] = rR[i] + rolling_hash(s[i]); } reverse(s.begin(),s.end()); set S; vector l,r; rep(i,n){ int ok = 0,ng = min(i,n-1-i) + 1; while(ng-ok>1){ int mid = (ok+ng)/2; if(check(R,rR,i-mid,i+mid+1))ok = mid; else ng = mid; } while(ok>=0){ auto tr = R[i+ok+1] - R[i-ok]; if(S.count(tr))break; S.insert(tr); l.push_back(i-ok); r.push_back(i+ok+1); ok--; } } rep(i,n-1){ if(s[i]!=s[i+1])continue; int ok = 0,ng = min(i,n-1-(i+1)) + 1; while(ng - ok > 1){ int mid = (ok+ng)/2; if(check(R,rR,i-mid,i+1+mid+1))ok = mid; else ng = mid; } while(ok>=0){ auto tr = R[i+1+ok+1] - R[i-ok]; if(S.count(tr))break; S.insert(tr); l.push_back(i-ok); r.push_back(i+1+ok+1); ok--; } } string st = s + " " + t; auto sa = suffix_array(st); auto la = lcp_array(st,sa); vector pos(s.size()); rep(i,sa.size()){ if(sa[i] seg(la); rep(i,l.size()){ int pp = pos[l[i]]; len = r[i] - l[i]; int L = seg.min_left(pp),R = seg.max_right(pp); R++; l[i] = L; r[i] = R; } fenwick_tree F(sa.size()); vector xy(l.size(),0); rep(i,sa.size()){ if(sa[i]