#285958 (C++14) No.263 Common Palindromes Extra

提出ソース

結果

問題	No.263 Common Palindromes Extra
ユーザー	akusyounin2412
提出日時	2018-09-18 16:38:55
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	6,275 bytes
コンパイル時間	1,795 ms
コンパイル使用メモリ	150,208 KB
実行使用メモリ	53,496 KB
最終ジャッジ日時	2024-07-18 08:01:35
合計ジャッジ時間	6,149 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	17 ms 14,080 KB
testcase_01	AC	4 ms 8,192 KB
testcase_02	AC	5 ms 8,192 KB
testcase_03	WA	-
testcase_04	RE	-
testcase_05	AC	123 ms 11,012 KB
testcase_06	AC	37 ms 8,960 KB
testcase_07	TLE	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
#include<fstream>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;
constexpr long long INF = numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourth; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)
LL h, w, n, m, k, t, s, p, q, last, first, cnt, sum, ans, dp[200000];
Fll a[300000], b[300000];
string str, ss;
bool f;
char c, ch[100][100];
int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
struct Edge { LL to, cost; };
vector<Edge>vec[200000];
vector<LL>v;
map<Fll, LL>ma;
multiset<LL>st;
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

struct PalindromicTree {
	//
	// private:
	struct node {
		map<char, int> link;
		int suffix_link;
		int len;
		int count;
	};

	vector<node> c;
	string s;
	int active_idx;

	node* create_node() {
		c.emplace_back();
		node* ret = &c.back();
		ret->count = 0;
		return ret;
	}

	// this->s の状態に依存する
	int find_prev_palindrome_idx(int node_id) {
		const int pos = int(s.size()) - 1;
		while (true) {
			const int 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(int v, int 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;
		node* size_0 = create_node(); // 長さ0のノードを作成
		size_0->suffix_link = 0; // 親は長さ-1のノード
		size_0->len = 0;

		active_idx = 0;
	}

	int get_active_idx() const {
		return active_idx;
	}
	node* get_node(int id) {
		return &c[id];
	}
	//add(c),stringを一文字ずつ追加
	void add(char ch) {
		s.push_back(ch);

		// ch + [A] + ch が回文となるものを探す
		const int a = find_prev_palindrome_idx(active_idx);

		//新しいノードへのリンクが発生するか試す
		const auto inserted_result = c[a].link.insert(make_pair(ch, int(c.size())));
		active_idx = inserted_result.first->second; // insertの成否に関わらず、iteratorが指す先は新しい回文のindex
		if (!inserted_result.second) {
			c[active_idx].count++; // その回文が現れた回数が増加
			return; // 既にリンクが存在したので、新しいノードを作る必要がない
		}

		// 実際に新しいノードを作成
		node* nnode = create_node();
		nnode->count = 1;
		nnode->len = c[a].len + 2; // ch + [A] + ch だから、長さは len(A) + 2

								   // suffix_linkの設定
		if (nnode->len == 1) {
			// この時だけsuffix_linkはsize 0に伸ばす
			nnode->suffix_link = 1;
		}
		else {
			// ch + [B] + ch が回文になるものを探す。ただし長さはaより小さいもの
			const int b = find_prev_palindrome_idx(c[a].suffix_link);
			nnode->suffix_link = c[b].link[ch];
		}
	}

	//各文字列が何回現れるか計算する
	// O(n)
	vector<int> build_frequency() {
		vector<int> frequency(c.size());
		//常に親ノードのid < 子ノードのidが成り立つので、idを大きい順から回せばよい
		for (int i = int(c.size()) - 1; i > 0; i--) {
			frequency[i] += c[i].count;
			frequency[c[i].suffix_link] += frequency[i];
		}
		return frequency;
	}

	// debug用
	// idがどのような回文を表しているのかを返す
	// O(n)
	string debug_id2string(int 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());
		int start = int(charas.size()) - 1;
		if (c[id].len % 2 == 1) start--;
		for (int i = start; i >= 0; i--) ret.push_back(charas[i]);

		return ret;
	}

	map<string, int> build_map() {
		vector<int> freq = build_frequency();
		map<string, int> ret;
		for (int i = 0; i < int(c.size()); i++) {
			const string palindrome = debug_id2string(i);
			ret[palindrome.c_str()] = freq[i];
		}
		return ret;
	}

	void display_frequencies() {
		auto freq = build_frequency();
		printf("frequencies of each palindrome...\n");
		for (int i = 0; i < int(c.size()); i++) {
			const string palindrome = debug_id2string(i);
			printf("  %s : %d\n", palindrome.c_str(), freq[i]);
		}
	}
};


int main() {
	PalindromicTree S, T;
	map<string, int>sm, tm;
	cin >> str;
	rep(i, str.size()) {
		S.add(str[i]);
	}
	sm = S.build_map();
	cin >> str;
	rep(i, str.size()) {
		T.add(str[i]);
	}
	tm = T.build_map();
	auto j = tm.begin(); auto i = sm.begin();
	i++;
	j++;
	i++;
	j++;
	for (; i != sm.end(); i++) {
		while (i->first > j->first&&j!=tm.end()) {
			j++;
		}
		if (j == tm.end())
			break;
		if (i->first == j->first) {
			ans += i->second*j->second;
		}
	}
	cout << ans << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード