#include using namespace std; /* #include using namespace atcoder; */ /* #include #include using bll = boost::multiprecision::cpp_int; using bdouble = boost::multiprecision::number>; using namespace boost::multiprecision; */ #ifdef LOCAL_TEST #define BOOST_STACKTRACE_USE_ADDR2LINE #define BOOST_STACKTRACE_ADDR2LINE_LOCATION /usr/local/opt/binutils/bin/addr2line #define _GNU_SOURCE 1 #include namespace std { template class dvector : public std::vector { public: dvector() : std::vector() {} explicit dvector(size_t n, const T& value = T()) : std::vector(n, value) {} dvector(const std::vector& v) : std::vector(v) {} dvector(const std::initializer_list il) : std::vector(il) {} dvector(const std::string::iterator first, const std::string::iterator last) : std::vector(first, last) {} dvector(const typename std::vector::iterator first, const typename std::vector::iterator last) : std::vector(first, last) {} dvector(const typename std::vector::reverse_iterator first, const typename std::vector::reverse_iterator last) : std::vector(first, last) {} dvector(const typename std::vector::const_iterator first, const typename std::vector::const_iterator last) : std::vector(first, last) {} dvector(const typename std::vector::const_reverse_iterator first, const typename std::vector::const_reverse_iterator last) : std::vector(first, last) {} T& operator[](size_t n) { try { return this->at(n); } catch (const std::exception& e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; return this->at(n); } } const T& operator[](size_t n) const { try { return this->at(n); } catch (const std::exception& e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; return this->at(n); } } }; } class dbool { private: bool boolvalue; public: dbool() : boolvalue(false) {} dbool(bool b) : boolvalue(b) {} operator bool&() { return boolvalue; } operator const bool&() const { return boolvalue; } }; #define vector dvector #define bool dbool class SIGFPE_exception : std::exception {}; class SIGSEGV_exception : std::exception {}; void catch_SIGFPE([[maybe_unused]] int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGFPE_exception(); } void catch_SIGSEGV([[maybe_unused]] int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGSEGV_exception(); } signed convertedmain(); signed main() { signal(SIGFPE, catch_SIGFPE); signal(SIGSEGV, catch_SIGSEGV); return convertedmain(); } #define main() convertedmain() #endif #ifdef LOCAL_DEV template std::ostream& operator<<(std::ostream& s, const std::pair& p) { return s << "(" << p.first << ", " << p.second << ")"; } template std::ostream& operator<<(std::ostream& s, const std::array& a) { s << "{ "; for (size_t i = 0; i < N; ++i){ s << a[i] << "\t"; } s << "}"; return s; } template std::ostream& operator<<(std::ostream& s, const std::set& se) { s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; } template std::ostream& operator<<(std::ostream& s, const std::multiset& se) { s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; } template std::ostream& operator<<(std::ostream& s, const std::map& m) { s << "{\n"; for (auto itr = m.begin(); itr != m.end(); ++itr){ s << "\t" << (*itr).first << " : " << (*itr).second << "\n"; } s << "}"; return s; } template std::ostream& operator<<(std::ostream& s, const std::deque& v) { for (size_t i = 0; i < v.size(); ++i){ s << v[i]; if (i < v.size() - 1) s << "\t"; } return s; } template std::ostream& operator<<(std::ostream& s, const std::vector& v) { for (size_t i = 0; i < v.size(); ++i){ s << v[i]; if (i < v.size() - 1) s << "\t"; } return s; } template std::ostream& operator<<(std::ostream& s, const std::vector>& vv) { s << "\\\n"; for (size_t i = 0; i < vv.size(); ++i){ s << vv[i] << "\n"; } return s; } void debug_impl() { std::cerr << '\n'; } template void debug_impl(Head head, Tail... tail) { std::cerr << " " << head << (sizeof...(tail) ? "," : ""); debug_impl(tail...); } #define debug(...) do { std::cerr << ":" << __LINE__ << " (" << #__VA_ARGS__ << ") ="; debug_impl(__VA_ARGS__); } while (false) #else #define debug(...) do {} while (false) #endif //#define int long long using ll = long long; //constexpr int INF = (ll)1e9 + 7; //INT_MAX = (1<<31)-1 = 2147483647 constexpr ll INF = (ll)1e18; //(1LL<<63)-1 = 9223372036854775807 constexpr ll MOD = (ll)1e9 + 7; //primitive root = 5 //constexpr ll MOD = 998244353; //primitive root = 3 constexpr double EPS = 1e-9; constexpr ll dx[4] = {1, 0, -1, 0}; constexpr ll dy[4] = {0, 1, 0, -1}; constexpr ll dx8[8] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr ll dy8[8] = {0, 1, 0, -1, 1, -1, 1, -1}; #define rep(i, n) for(ll i=0, i##_length=(n); i< i##_length; ++i) #define repeq(i, n) for(ll i=1, i##_length=(n); i<=i##_length; ++i) #define rrep(i, n) for(ll i=(n)-1; i>=0; --i) #define rrepeq(i, n) for(ll i=(n) ; i>=1; --i) #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() void p() { std::cout << '\n'; } template void p(Head head, Tail... tail) { std::cout << head << (sizeof...(tail) ? " " : ""); p(tail...); } template inline void pv(std::vector& v) { for(ll i=0, N=v.size(); i inline bool chmax(T& a, T b) { return a < b && (a = b, true); } template inline bool chmin(T& a, T b) { return a > b && (a = b, true); } template inline void uniq(std::vector& v) { v.erase(std::unique(v.begin(), v.end()), v.end()); } /*-----8<-----template-----8<-----*/ //https://math314.hateblo.jp/entry/2016/12/19/005919 struct PalindromicTree { // private: struct node { //回文の次の文字,cのインデックス 緑色の線 map link; //親ノードのID 灰色の線 ll suffix_link; //回文長 ll len; //出現回数 ll count; //親からの深さ = このノードが末尾となる異なる長さの回文の数 ll depth; }; vector c; string s; ll active_idx; //indexes[i] := i文字目のノードのインデックス(c[indexes[i]]でノードが得られる) vector indexes; node* create_node() { c.emplace_back(); node* ret = &c.back(); ret->count = 0; return ret; } // this->s の状態に依存する ll find_prev_palindrome_idx(ll node_id) { const ll pos = ll(s.size()) - 1; while (true) { const ll opposite_side_idx = pos - 1 - c[node_id].len; if (opposite_side_idx >= 0 && s[opposite_side_idx] == s.back()) break; node_id = c[node_id].suffix_link; // 次の回文に移動 } return node_id; } bool debug_id2string_dfs(ll v, ll id, vector& charas) { if (v == id) return true; for (auto&& kv : c[v].link) { if (debug_id2string_dfs(kv.second, id, charas)) { charas.push_back(kv.first); return true; } } return false; } public: PalindromicTree() { node* size_m1 = create_node(); // 長さ-1のノードを作成 size_m1->suffix_link = 0; // -1 の親suffixは自分自身 size_m1->len = -1; size_m1->depth = 0; node* size_0 = create_node(); // 長さ0のノードを作成 size_0->suffix_link = 0; // 親は長さ-1のノード size_0->len = 0; size_0->depth = 0; active_idx = 0; } ll get_active_idx() const { return active_idx; } //ユニークな回文の数を返す ll unique_size() { return c.size()-2; } //i文字目のノードを返す node* get_node(ll i) { ll nodeindex = indexes[i]; return &c[nodeindex]; } //文字列末尾に ch を追加 void add(char ch) { s.push_back(ch); // ch + [A] + ch が回文となるものを探す const ll a = find_prev_palindrome_idx(active_idx); //新しいノードへのリンクが発生するか試す const auto inserted_result = c[a].link.insert(make_pair(ch, ll(c.size()))); active_idx = inserted_result.first->second; // insertの成否に関わらず、iteratorが指す先は新しい回文のindex if (!inserted_result.second) { indexes.push_back(active_idx); c[active_idx].count++; // その回文が現れた回数が増加 return; // 既にリンクが存在したので、新しいノードを作る必要がない } // 実際に新しいノードを作成 node* nnode = create_node(); nnode->count = 1; nnode->len = c[a].len + 2; // ch + [A] + ch だから、長さは len(A) + 2 nnode->depth = c[a].depth + 1; indexes.push_back(c.size()-1); // suffix_linkの設定 if (nnode->len == 1) { // この時だけsuffix_linkはsize 0に伸ばす nnode->suffix_link = 1; } else { // ch + [B] + ch が回文になるものを探す。ただし長さはaより小さいもの const ll b = find_prev_palindrome_idx(c[a].suffix_link); nnode->suffix_link = c[b].link[ch]; } } //各文字列が何回現れるか計算する frequency[idx]=ノードc[idx]の回文の出現回数 // O(n) vector build_frequency() { vector frequency(c.size()); //常に親ノードのid < 子ノードのidが成り立つので、idを大きい順から回せばよい for (ll i = ll(c.size()) - 1; i > 0; i--) { frequency[i] += c[i].count; frequency[c[i].suffix_link] += frequency[i]; } return frequency; } // debug用 // c[id]がどのような回文を表しているのかを返す // O(n) string debug_id2string(ll id) { if (id == 0) { return "(-1)"; } else if (id == 1) { return "(0)"; } vector charas; debug_id2string_dfs(0, id, charas); debug_id2string_dfs(1, id, charas); string ret(charas.begin(),charas.end()); ll start = ll(charas.size()) - 1; if (c[id].len % 2 == 1) start--; for (ll i = start; i >= 0; i--) ret.push_back(charas[i]); return ret; } void display_frequencies() { auto freq = build_frequency(); cerr << "frequencies of each palindrome...\n"; for (ll i = 0; i < ll(c.size()); i++) { const string palindrome = debug_id2string(i); cerr << " " << palindrome << " : " << freq[i] << "\n"; } } }; /*-----8<-----library-----8<-----*/ //https://yukicoder.me/problems/no/263 void yuki263() { string S,T; cin>>S>>T; PalindromicTree pts, ptt; rep(i,S.size())pts.add(S[i]); rep(i,T.size())ptt.add(T[i]); vector freqs=pts.build_frequency(); vector freqt=ptt.build_frequency(); ll ans=0; auto f=[&](auto&& f, ll sindex, ll tindex)->void{ if(sindex>1 && tindex>1)ans+=freqs[sindex]*freqt[tindex]; for(auto&& spr:pts.c[sindex].link){ auto it=ptt.c[tindex].link.find(spr.first); if(it!=ptt.c[tindex].link.end()){ f(f,spr.second,it->second); } } }; f(f,0,0); f(f,1,1); p(ans); } void solve() { PalindromicTree pt; using Node = decltype(pt)::node; string s = "abcabccbc"; for (ll i=0; i<(ll)s.size(); i++) { debug(s.substr(0,i+1)); pt.add(s[i]); // 1文字ずつ登録していく pt.display_frequencies(); //i文字目のノードを取得 Node* node=pt.get_node(i); debug(node->depth); debug(node->len); debug(node->count); debug("-----------------"); } //ユニークな回文の数 debug(pt.unique_size()); } signed main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); //ll Q; cin >> Q; while(Q--)solve(); ///solve(); yuki263(); return 0; }