結果

問題 No.263 Common Palindromes Extra
ユーザー kwm_t
提出日時 2025-03-01 16:31:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 285 ms / 2,000 ms
コード長 3,582 bytes
コンパイル時間 3,768 ms
コンパイル使用メモリ 291,236 KB
実行使用メモリ 178,984 KB
最終ジャッジ日時 2025-03-01 16:31:47
合計ジャッジ時間 5,876 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
#define endl "\n"
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
template<typename T = char>
struct PalindromicTree {
public:
	struct Node {
		std::map<T, int>link;	// child node index
		int suffixLink;			// 最長回文suffixのindex
		int length;				// 回分の長さ
		std::vector<int>index;	// suffixLinkをこのNodeに貼るstring上のindex
		int deltaLink;			// 差分が異なる最長回文接尾辞のindex

		Node() {}
		Node(int suffixLink_, int length_) :suffixLink(suffixLink_), length(length_), deltaLink(-1) {}
	};

	std::vector<Node>nodes;
	int pointer;
	std::vector<T>vs;

private:
	int find_prev_palindrome(int cur) const {
		int pos = (int)vs.size() - 1;
		while (true) {
			int rev = pos - nodes[cur].length - 1;
			if (rev >= 0 && vs[rev] == vs.back())break;
			cur = nodes[cur].suffixLink;
		}
		return cur;
	}
	int diff(int index) const {
		// 最長回文接尾辞との差分を返す
		if (nodes[index].suffixLink <= 0)return -1;
		return nodes[index].length - nodes[nodes[index].suffixLink].length;
	}
	// output_dfs
public:
	PalindromicTree() :pointer(0) {
		// dummyの頂点
		nodes.emplace_back(0, -1);
		nodes.emplace_back(0, 0);
	}
	PalindromicTree(const std::string &s) : PalindromicTree() {
		add(s);
	}
	void add(const std::string&s) {
		for (auto &c : s)add(c);
	}
	int add(const T &c) {
		int index = (int)vs.size();
		vs.push_back(c);
		int cur = find_prev_palindrome(pointer);
		auto res = nodes[cur].link.insert(std::make_pair(c, (int)nodes.size()));
		pointer = res.first->second;
		if (res.second) {// add new node
			nodes.emplace_back(-1, nodes[cur].length + 2);
			// set suffix link
			if (nodes.back().length == 1) {
				nodes.back().suffixLink = 1;
			}
			else {
				nodes.back().suffixLink = nodes[find_prev_palindrome(nodes[cur].suffixLink)].link[c];
			}
			if (diff(pointer) == diff(nodes.back().suffixLink)) {
				nodes.back().deltaLink = nodes[nodes.back().suffixLink].deltaLink;
			}
			else {
				nodes.back().deltaLink = nodes.back().suffixLink;
			}
		}
		nodes[pointer].index.emplace_back(index);
		return pointer;
	}
	// update_dp
	// build_frequency
	// output
	int size()const { return(int)nodes.size(); }
	Node &operator[](int index) { return nodes[index]; }
};
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	using namespace std;
	string S, T; cin >> S >> T;
	PalindromicTree tree(S + "><" + T);
	vector< int > dps(1111111), dpt(1111111);
	for (int i = 0; i < tree.size(); i++) {
		for (auto &j : tree[i].index) {
			if (j < (int)S.size()) ++dps[i];
			else if (j >= (int)S.size() + 2) ++dpt[i];
		}
	}
	long long ret = 0;
	for (int i = tree.size() - 1; i > 1; i--) {
		ret += 1LL * dps[i] * dpt[i];
		dps[tree[i].suffixLink] += dps[i];
		dpt[tree[i].suffixLink] += dpt[i];
	}
	cout << ret << "\n";
	return 0;
}
0