結果

問題 No.2606 Mirror Relay
コンテスト
ユーザー Aeren
提出日時 2024-01-12 23:35:16
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 3,196 bytes
コンパイル時間 3,660 ms
コンパイル使用メモリ 268,060 KB
実行使用メモリ 52,588 KB
最終ジャッジ日時 2024-09-28 00:20:01
合計ジャッジ時間 5,546 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 69
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif

template<class F>
struct y_combinator_result{
	F f;
	template<class T> explicit y_combinator_result(T &&f): f(forward<T>(f)){ }
	template<class ...Args> decltype(auto) operator()(Args &&...args){ return f(ref(*this), forward<Args>(args)...); }
};
template<class F>
decltype(auto) y_combinator(F &&f){
	return y_combinator_result<decay_t<F>>(forward<F>(f));
}

// Each node represents a unique palindromic substring plus 0 and 1 node representing empty even and odd string
// Adjacency_Type: array<int, X> or map<Char_Type, int> where X is the size of the alphabet
template<class Char_Type, class Adjacency_Type>
struct palindrome_automaton{
	// Begin States
	// len: length of the palindrome
	// link: suffix link
	// serial_link[u]: longest proper suffix v with len[u] - len[link[u]] != len[v] - len[link[v]]
	// depth: # of suffix links till root
	// occurence: # of occurences of the palindrome as a longest proper palindromic suffix of a prefix
	vector<int> len{0, -1}, link{1, 0}, serial_link{0, 0}, depth{0, 0}, occurence{1, 0};
	vector<Adjacency_Type> next = vector<Adjacency_Type>(2);
	// End States
	vector<Char_Type> s{-1};
	vector<int> last{0};
	long long palindromic_substring_count = 0;
	int new_state(int l, int u){
		len.push_back(l);
		link.push_back(u);
		serial_link.push_back(l - len[u] == len[u] - len[link[u]] ? serial_link[u] : u);
		depth.push_back(depth[u] + 1);
		next.emplace_back();
		occurence.push_back(0);
		return (int)len.size() - 1;
	}
	void extend(const vector<Char_Type> &s){
		for(auto c: s) extend(c);
	}
	void extend(Char_Type c){
		s.push_back(c);
		int l = last.back();
		while(s[(int)s.size() - len[l] - 2] != s.back()) l = link[l];
		if(!next[l][c]){
			int u = link[l];
			while(s[(int)s.size() - len[u] - 2] != s.back()) u = link[u];
			int v = new_state(len[l] + 2, next[u][c]);
			next[l][c] = v; // Separated for UB in C++14 or below
		}
		last.push_back(next[l][c]);
		palindromic_substring_count += depth[last.back()];
		++ occurence[last.back()];
	}
	int size() const{ // # of states
		return (int)len.size();
	}
	// count: # of occurences of the palindrome
	vector<int> count;
	vector<vector<int>> inv_link;
	void init_count(){
		count = occurence, inv_link.assign(size(), {});
		for(auto u = 2; u < (int)size(); ++ u) inv_link[link[u]].push_back(u);
		auto dfs = [&](auto self, int u)->void{
			for(auto v: inv_link[u]) self(self, v), count[u] += count[v];
		};
		dfs(dfs, 0);
	}
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	vector<int> s;
	{
		string t;
		cin >> t;
		for(auto c: t){
			s.push_back(c - 'a');
		}
	}
	const int mx = 26;
	palindrome_automaton<int, array<int, mx>> aut;
	aut.extend(s);
	aut.init_count();
	vector<long long> res(aut.size());
	for(auto s = 0; s < 2; ++ s){
		y_combinator([&](auto self, int u)->void{
			res[u] += 1LL * aut.count[u] * max(0, aut.len[u]);
			for(auto v: aut.inv_link[u]){
				if(v <= 1){
					continue;
				}
				res[v] += res[u];
				self(v);
			}
		})(s);
	}
	cout << ranges::max(res) << "\n";
	return 0;
}

/*

*/
0