#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef DEBUG #include "./Lib/debug.hpp" #include "./Lib/Timer.hpp" #include "./Lib/sample.hpp" #else #define dump(...) #endif /* (=^o^=) */ //#define int ll /* macro */ #define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i) #define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i) #define REP(i, n) FOR(i, 0, n) #define RREP(i, n) RFOR(i, 0, n) #define REPC(x,c) for(const auto& x:(c)) #define REPI2(it,b,e) for(auto it = (b); it != (e); ++it) #define REPI(it,c) REPI2(it, (c).begin(), (c).end()) #define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend()) #define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);) #define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end()) #define ALL(x) (x).begin(),(x).end() #define cauto const auto& /* macro func */ template inline void sort(T& t) { std::sort(ALL(t)); } template inline void rsort(T& t) { std::sort((t).rbegin(), (t).rend()); } template inline void unique(T& t) { (t).erase(unique((t).begin(), (t).end()), (t).end()); } template inline bool chmax(T& t, const S& s) { if (s > t) { t = s; return true; } return false; } template inline bool chmaxE(T& t, const S& s) { if (s >= t) { t = s; return true; } return false; } template inline bool chmin(T& t, const S& s) { if (s < t) { t = s; return true; } return false; } inline void BR() { std::cout << "\n"; } /* type define */ using ll = long long; using PAIR = std::pair; using VS = std::vector; using VL = std::vector; using VVL = std::vector; using VVVL = std::vector; using VD = std::vector; template using V = std::vector; /* using std */ using std::cout; constexpr char endl = '\n'; using std::cin; using std::pair; using std::string; using std::stack; using std::queue; using std::vector; using std::list; using std::map; using std::unordered_map; using std::multimap; using std::unordered_multimap; using std::set; using std::unordered_set; using std::unordered_multiset; using std::multiset; using std::bitset; using std::priority_queue; using std::tuple; /* constant value */ constexpr ll MOD = 1000000007; //constexpr ll MOD = 998244353; /* Initial processing */ struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing; /* Remove the source of the bug */ inline signed pow(signed, signed) { assert(false); return -1; } /* define hash */ namespace std { template <> class hash> { public: size_t operator()(const std::pair& x) const { return hash()(1000000000 * x.first + x.second); } }; } /* input */ template std::istream& operator >> (std::istream& is, vector& vec) { for (T& x : vec) is >> x; return is; } //============================================================================================= constexpr auto nullLambda = [](int, const std::list&) {}; class PalindromicTree { //static constexpr auto nullLambda = [](int, const std::list&) {};// c++17 class Node :public std::enable_shared_from_this { // 最大の回文接尾辞 std::weak_ptr m_suffixLink; // 次サイズの回文(囲む文字, 次のNode) std::unordered_map> m_edges; // 回文の右端itr std::list m_itrs; // 回文サイズ const int m_size; // xAxとなるAを探す(x=str[itr]) auto find(int itr, const std::string& s, bool flg = false) { // rootにたどり着いた if (m_size == -1) { return weak_from_this(); } // 現在地"A"において"xAx"となる if (itr - m_size - 1 >= 0 && s[itr] == s[itr - m_size - 1]) { return weak_from_this(); } // 見つからない return m_suffixLink.lock()->find(itr, s, flg); } // 新しい回文Nodeを作成する auto create(int itr, const std::string& s) { // suffixLinkの探索 auto suffixLinkFrom = m_suffixLink.lock()/*->m_suffixLink.lock()*/->find(itr, s, true).lock(); // 新Nodeの作成 auto newNode = std::make_shared( m_size + 2, (suffixLinkFrom->m_edges.find(s[itr]) == suffixLinkFrom->m_edges.end()) ? suffixLinkFrom->m_edges.find(' ')->second : suffixLinkFrom->m_edges.find(s[itr])->second); m_edges.emplace(s[itr], newNode); return std::weak_ptr(newNode); } public: // constructor Node(int size, const std::weak_ptr& suffixLink) : m_size(size), m_suffixLink(suffixLink) { m_edges.reserve(size); } Node() :m_size(-1) {} // 次サイズの回文を追加 auto add(int itr, const std::string& s) { auto addRoot = find(itr, s).lock(); auto nextNode = (addRoot->m_edges.find(s[itr]) == addRoot->m_edges.end()) ? addRoot->create(itr, s) : std::weak_ptr(addRoot->m_edges.find(s[itr])->second); nextNode.lock()->m_itrs.emplace_back(itr); return nextNode; } // debug用 auto outputTree(const std::string& s) ->void const { if (m_size <= 0) { cout << "root"; } else { // 段 for (int i = 0; (i < (m_size + 1) / 2); ++i) { cout << " |"; } cout << "- " << s.substr(*m_itrs.begin() - m_size + 1, m_size); // 右itr cout << " [ "; for (const auto& itr : m_itrs) { cout << itr << " "; }cout << "] "; // suffix link //auto p = m_suffixLink.lock(); //cout << "{" << s.substr(*p->m_itrs.begin() - p->m_size + 1, p->m_size) << "} "; } cout << "\n"; for (const auto& edge : m_edges) { if (m_size == -1 && edge.first == ' ') { continue; } edge.second->outputTree(s); } } // rootを決定 auto isOddRoot(const std::weak_ptr& evenRoot) { m_suffixLink = weak_from_this(); m_edges.emplace(' ', evenRoot); } // ラムダ式の実行 template auto runLambda(const Lambda& lambda) { if (m_size > 0) { lambda(m_size, m_itrs); } } /* * lambda: (int size, list rItr) -> void */ template auto dfs_edges(const Lambda& lambda, const SuffixLinkLambda& slLambda = nullLambda)->void { runLambda(lambda); m_suffixLink.lock()->runLambda(slLambda); for (const auto& edge : m_edges) { edge.second->dfs_edges(lambda, slLambda); } } }; // 対象となる文字列 const std::string m_s; // 偶数長,奇数長のPalindromicTreeの根(0, -1) std::shared_ptr m_rootOdd; std::shared_ptr m_rootEven; public: // constructor PalindromicTree(const std::string& s) : m_s(s), m_rootOdd(std::make_shared()), m_rootEven(std::make_shared(0, m_rootOdd)) { m_rootOdd->isOddRoot(m_rootEven); auto root = m_rootOdd; for (int r = 0; r < s.size(); ++r) { root = root->add(r, s).lock(); } } /* * lambda: (int size, list rItr) -> void */ template auto dfs_edges(const Lambda& lambda) { m_rootOdd->dfs_edges(lambda); } /* * かなり強引な実装 * lambda: (int from, int to) -> void */ template auto dp_suffixLink(const Lambda& lambda) { // 森の生成,探索順序の決定 int from; std::unordered_map graph; graph.reserve(m_s.size()); std::vector orderCount(m_s.size()); m_rootOdd->dfs_edges([&](int size, const std::list& rItrs) { from = rItrs.front(); }, [&](int size, const std::list& rItrs) { int to = rItrs.front(); graph.emplace(from, to); ++orderCount[to]; }); // 探索順序に従って処理 std::queue q; for (int i = 0; i < m_s.size(); ++i)if (orderCount[i] == 0) { q.emplace(i); } while (!q.empty()) { int from = q.front(); q.pop(); auto range = graph.equal_range(from); for (auto itr = range.first; itr != range.second; ++itr) { int to = itr->second; --orderCount[to]; lambda(from, to); if (orderCount[to] == 0) { q.emplace(to); } } } } // debug用 auto outputTree() { dump(m_s); cout << "-- even --\n"; m_rootEven->outputTree(m_s); cout << "-- odd --\n"; m_rootOdd->outputTree(m_s); } }; signed main() { string a, b; cin >> a >> b; string s = a + "$%" + b; ll n = s.size(); ll an = a.size(); auto tree = PalindromicTree(s); V dp(n); tree.dfs_edges([&](int size, const list& ritr) { ll l = 0, r = 0; REPC(x, ritr) if (x != an && x != an + 1) { ++((x < an) ? l : r); } dp[ritr.front()] = {l,r}; }); tree.dp_suffixLink([&](int from, int to) { dp[to].first += dp[from].first; dp[to].second += dp[from].second; }); ll ans = 0; REPC(p, dp) { ans += (p.first * p.second); } cout << ans << endl; dump(dp); //tree.outputTree(); }