結果

問題 No.263 Common Palindromes Extra
ユーザー kyon2326kyon2326
提出日時 2020-09-16 21:21:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 217 ms / 2,000 ms
コード長 11,830 bytes
コンパイル時間 2,383 ms
コンパイル使用メモリ 228,344 KB
実行使用メモリ 172,008 KB
最終ジャッジ日時 2024-06-22 03:37:21
合計ジャッジ時間 4,187 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 9 ms
6,940 KB
testcase_04 AC 37 ms
17,940 KB
testcase_05 AC 59 ms
17,456 KB
testcase_06 AC 6 ms
6,940 KB
testcase_07 AC 126 ms
98,220 KB
testcase_08 AC 145 ms
98,200 KB
testcase_09 AC 217 ms
172,008 KB
testcase_10 AC 162 ms
162,196 KB
testcase_11 AC 29 ms
17,080 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
/*
#include <atcoder/all>
using namespace atcoder;
*/
/*
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using bll = boost::multiprecision::cpp_int;
using bdouble = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>;
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 <boost/stacktrace.hpp>
	namespace std {
		template<typename T> class dvector : public std::vector<T> {
		public:
			dvector() : std::vector<T>() {}
			explicit dvector(size_t n, const T& value = T()) : std::vector<T>(n, value) {}
			dvector(const std::vector<T>& v) : std::vector<T>(v) {}
			dvector(const std::initializer_list<T> il) : std::vector<T>(il) {}
			dvector(const std::string::iterator first, const std::string::iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::iterator first, const typename std::vector<T>::iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::reverse_iterator first, const typename std::vector<T>::reverse_iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::const_iterator first, const typename std::vector<T>::const_iterator last) : std::vector<T>(first, last) {}
			dvector(const typename std::vector<T>::const_reverse_iterator first, const typename std::vector<T>::const_reverse_iterator last) : std::vector<T>(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<typename T1, typename T2> std::ostream& operator<<(std::ostream& s, const std::pair<T1, T2>& p) {
		return s << "(" << p.first << ", " << p.second << ")"; }
	template <typename T, size_t N> std::ostream& operator<<(std::ostream& s, const std::array<T, N>& a) {
		s << "{ "; for (size_t i = 0; i < N; ++i){ s << a[i] << "\t"; } s << "}"; return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::set<T>& se) {
		s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::multiset<T>& se) {
		s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; }
	template<typename T1, typename T2> std::ostream& operator<<(std::ostream& s, const std::map<T1, T2>& m) {
		s << "{\n"; for (auto itr = m.begin(); itr != m.end(); ++itr){ s << "\t" << (*itr).first << " : " << (*itr).second << "\n"; } s << "}"; return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::deque<T>& v) {
		for (size_t i = 0; i < v.size(); ++i){ s << v[i]; if (i < v.size() - 1) s << "\t"; } return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::vector<T>& v) {
		for (size_t i = 0; i < v.size(); ++i){ s << v[i]; if (i < v.size() - 1) s << "\t"; } return s; }
	template<typename T> std::ostream& operator<<(std::ostream& s, const std::vector<std::vector<T>>& 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<typename Head, typename... Tail> 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<typename Head, typename... Tail> void p(Head head, Tail... tail) { std::cout << head << (sizeof...(tail) ? " " : ""); p(tail...); }
template<typename T> inline void pv(std::vector<T>& v) { for(ll i=0, N=v.size(); i<N; i++) std::cout << v[i] << " \n"[i==N-1]; }
template<typename T> inline bool chmax(T& a, T b) { return a < b && (a = b, true); }
template<typename T> inline bool chmin(T& a, T b) { return a > b && (a = b, true); }
template<typename T> inline void uniq(std::vector<T>& 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<char, ll> link;
		//親ノードのID 灰色の線
		ll suffix_link;
		//回文長
		ll len;
		//出現回数
		ll count;
		//親からの深さ = このノードが末尾となる異なる長さの回文の数
		ll depth;
	};

	vector<node> c;
	string s;
	ll active_idx;
	//indexes[i] := i文字目のノードのインデックス(c[indexes[i]]でノードが得られる)
	vector<ll> 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<char>& 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<ll> build_frequency() {
		vector<ll> 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<char> 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<ll> freqs=pts.build_frequency();
	vector<ll> 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;
}
0