This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM https://yukicoder.me/problems/399 #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../string/palindromictree.cpp" #include "../../string/rollinghash.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; string s,t; cin>>s>>t; PalindromicTree p1(s),p2(t); const int MOD = 1e9+7; const int BASE1 = 1777771; const int BASE2 = 1e6+3; RollingHash<int, MOD, BASE1> rs1(s),rt1(t); RollingHash<int, MOD, BASE2> rs2(s),rt2(t); const int MAX = 5e5+100; map<pair<int, int>, int> m1[MAX]; for(int i=2;i<(int)p1.size();i++){ auto& u=p1.vs[i]; if(u.app<0) continue; auto p=make_pair(rs1.find(u.app,u.app+u.len), rs2.find(u.app,u.app+u.len)); m1[u.len][p]=u.cnt; } ll ans=0; for(int i=2;i<(int)p2.size();i++){ auto& u=p2.vs[i]; auto p=make_pair(rt1.find(u.app,u.app+u.len), rt2.find(u.app,u.app+u.len)); if(u.app<0||!m1[u.len].count(p)) continue; ans+=(ll)m1[u.len][p]*u.cnt; } cout<<ans<<endl; return 0; }
#line 1 "test/yukicoder/0399.test.cpp" // verification-helper: PROBLEM https://yukicoder.me/problems/399 #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "string/palindromictree.cpp" #line 3 "string/palindromictree.cpp" using namespace std; #endif //BEGIN CUT HERE struct PalindromicTree{ struct node{ map<char, int> nxt; int len,suf,app,cnt; node():len(-1){} node(int len,int suf,int app,int cnt) :len(len),suf(suf),app(app),cnt(cnt){} }; vector<node> vs; vector<int> ord; int n,ptr; PalindromicTree(const string &s) :vs(s.size()+10),n(2),ptr(1){ vs[0]=node(-1,0,-1,0); vs[1]=node( 0,0,-1,0); for(int i=0;i<(int)s.size();i++) add_char(s,i); calc_order(); calc_count(); } bool add_char(const string &s,int pos){ char ch=s[pos]; int cur=ptr; while(1){ int rev=pos-1-vs[cur].len; if(rev>=0 and s[rev]==ch) break; cur=vs[cur].suf; } if(vs[cur].nxt.count(ch)){ ptr=vs[cur].nxt[ch]; vs[ptr].cnt++; return false; } ptr=n++; vs[ptr]=node(vs[cur].len+2,-1,pos-vs[cur].len-1,1); vs[cur].nxt[ch]=ptr; if(vs[ptr].len==1){ vs[ptr].suf=1; return true; } while(1){ cur=vs[cur].suf; int rev=pos-1-vs[cur].len; if(rev>=0 and s[rev]==ch){ vs[ptr].suf=vs[cur].nxt[ch]; break; } } return true; } void calc_order(){ ord.clear(); ord.emplace_back(0); ord.emplace_back(1); for(int i=0;i<(int)ord.size();i++) for(auto &p:vs[ord[i]].nxt) ord.emplace_back(p.second); } void calc_count(){ for(int i=(int)ord.size()-1;i>=0;i--) vs[vs[ord[i]].suf].cnt+=vs[ord[i]].cnt; } size_t size()const{return n;} }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 1 "string/rollinghash.cpp" #line 3 "string/rollinghash.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T,T MOD,T B> struct RollingHash{ using ll = long long; vector<T> hash,po; RollingHash(vector<T> vs){init(vs);} RollingHash(string &s){ vector<T> vs; for(char c:s) vs.emplace_back(c); init(vs); } void init(vector<T> vs){ int n=vs.size(); hash.assign(n+1,0); po.assign(n+1,1); for(int i=0;i<n;i++){ hash[i+1]=((ll)hash[i]*B+vs[i])%MOD; po[i+1]=(ll)po[i]*B%MOD; } } //S[l, r) T find(int l,int r){ T res=(ll)hash[r]+MOD-(ll)hash[l]*po[r-l]%MOD; return res>=MOD?res-MOD:res; } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 9 "test/yukicoder/0399.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); using ll = long long; string s,t; cin>>s>>t; PalindromicTree p1(s),p2(t); const int MOD = 1e9+7; const int BASE1 = 1777771; const int BASE2 = 1e6+3; RollingHash<int, MOD, BASE1> rs1(s),rt1(t); RollingHash<int, MOD, BASE2> rs2(s),rt2(t); const int MAX = 5e5+100; map<pair<int, int>, int> m1[MAX]; for(int i=2;i<(int)p1.size();i++){ auto& u=p1.vs[i]; if(u.app<0) continue; auto p=make_pair(rs1.find(u.app,u.app+u.len), rs2.find(u.app,u.app+u.len)); m1[u.len][p]=u.cnt; } ll ans=0; for(int i=2;i<(int)p2.size();i++){ auto& u=p2.vs[i]; auto p=make_pair(rt1.find(u.app,u.app+u.len), rt2.find(u.app,u.app+u.len)); if(u.app<0||!m1[u.len].count(p)) continue; ans+=(ll)m1[u.len][p]*u.cnt; } cout<<ans<<endl; return 0; }