結果

問題 No.263 Common Palindromes Extra
ユーザー antaanta
提出日時 2015-07-25 16:36:00
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 93 ms / 2,000 ms
コード長 6,544 bytes
コンパイル時間 1,381 ms
コンパイル使用メモリ 100,460 KB
実行使用メモリ 32,464 KB
最終ジャッジ日時 2023-08-20 00:29:39
合計ジャッジ時間 2,594 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 8 ms
5,060 KB
testcase_04 AC 30 ms
12,812 KB
testcase_05 AC 73 ms
12,852 KB
testcase_06 AC 4 ms
4,376 KB
testcase_07 AC 31 ms
19,356 KB
testcase_08 AC 64 ms
18,248 KB
testcase_09 AC 25 ms
22,648 KB
testcase_10 AC 30 ms
32,464 KB
testcase_11 AC 93 ms
12,904 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

struct PalindromicTree {
	typedef int Index;
	typedef char Alpha;
	struct Node {
		//回文の長さ
		Index length;
		//文字列 A が親の回文で、文字 b に対して bAb が自分の回文のとき、border == b となる。
		Alpha border;
		Index head, next;
		//最長接尾回文。S[i,j]がこのnodeの回文の時、S[k,j] (i < k) がnode->suffixの回文となる。
		Index suffix;
		Node() { }
		Node(Index length_, Alpha border_, Index next_, Index suffix_):
			length(length_), border(border_), head(-1), next(next_), suffix(suffix_) { }
	};

	Index nNodes;
	//親→子, suffix link の両方での逆トポロジカル順序で並んでいる。
	vector<Node> nodes;
	vector<Alpha> alphas;

	void init(Index n) {
		assert(n >= 0);
		nodes.resize(n + 2);
		nodes[0] = Node(-1, '\0', -1, -1);
		nodes[1] = Node(0, '\0', -1, 0);
		nNodes = 2;
		alphas.resize(n);
	}

	//長さ-1扱いで、全ての奇回文の根
	Index getOddRoot() const { return 0; }
	//長さ0扱いで、全ての偶回文の根。
	//また、空文字列として、空以外に接尾回文が存在しない場合のsuffixの先となる。
	Index getEvenRoot() const { return 1; }

	Index findChild(Index i, Alpha alpha) const {
		Index c = nodes[i].head;
		while(c != -1) {
			if(nodes[c].border == alpha)
				return c;
			c = nodes[c].next;
		}
		return -1;
	}

	Index findSuffixExtension(Index i, Index pos, Index beginningPos) const {
		while(1) {
			Index len = nodes[i].length, left = pos - 1 - len;
			if(beginningPos <= left && alphas[left] == alphas[pos])
				return i;
			i = nodes[i].suffix;
		}
	}

	bool processAlphabet(Index &activeIndex, Index pos, Index beginningPos) {
		Alpha alpha = alphas[pos];
		Index parentIndex = findSuffixExtension(activeIndex, pos, beginningPos);
		Index childIndex = findChild(parentIndex, alpha);

		if(childIndex != -1) {
			activeIndex = childIndex;
			return false;
		}
		Node &parent = nodes[parentIndex];

		Index suffixIndex;
		if(parent.length == -1) {
			suffixIndex = getEvenRoot();
		}else {
			Index suffixParentIndex = findSuffixExtension(parent.suffix, pos, beginningPos);
			suffixIndex = findChild(suffixParentIndex, alpha);
		}

		childIndex = nNodes ++;
		nodes[childIndex] = Node(parent.length + 2, alpha, parent.head, suffixIndex);
		activeIndex = parent.head = childIndex;
		return true;
	}

	//追加のデータを処理する必要がある場合、
	//これを参考にprocessAlphabetを1回ずつ呼んでactiveIndexを見ればよい。
	void addString(const Alpha *str, Index len, Index beginningPos = 0) {
		Index activeIndex = getEvenRoot();
		for(Index i = 0; i < len; ++ i) {
			alphas[beginningPos + i] = str[i];
			processAlphabet(activeIndex, beginningPos + i, beginningPos);
		}
	}

	void addStringCountFreq(const Alpha *str, Index len, vector<Index> &freq, Index beginningPos = 0) {
		freq.assign(nodes.size(), 0);
		Index activeIndex = getEvenRoot();
		for(Index i = 0; i < len; ++ i) {
			alphas[beginningPos + i] = str[i];
			processAlphabet(activeIndex, beginningPos + i, beginningPos);
			++ freq[activeIndex];
		}
		//"ある接頭詞の接尾回文"として全て列挙できることに注意
		for(Index i = nNodes - 1; i > 0; -- i)
			freq[nodes[i].suffix] += freq[i];
	}
};



void readSpace() { int c = getchar(); assert(c == ' '); }
static bool read_eof = false;
void readEOL() {
	int c = getchar();
	if(c == EOF) {
		assert(!read_eof);
		read_eof = true;
	}else {
		assert(c == '\n');
	}
}

int readString(char *buf, int minLen, int maxLen, bool charactors[128]) {
	assert(0 <= minLen && minLen <= maxLen);
	int len = 0;
	while(1) {
		int c = getchar();
		if(!(0 <= c && c < 128) || !charactors[c]) {
			ungetc(c, stdin);
			break;
		}
		assert(len < maxLen);
		buf[len ++] = c;
	}
	assert(minLen <= len && len <= maxLen);
	buf[len] = 0;
	return len;
}

int test() {
	cerr << "test" << endl;
	string S, T;
	rep(ii, 1000000) {
		int lenS = rand() % 10 + 1, lenT = rand() % 10 + 1;
		int A = rand() % 10 + 1;
		S.resize(lenS); T.resize(lenT);
		rep(i, lenS) S[i] = 'A' + rand() % A;
		rep(i, lenT) T[i] = 'A' + rand() % A;

		PalindromicTree pt;
		pt.init(lenS + lenT);
		vector<int> freqS, freqT;
		pt.addStringCountFreq(S.c_str(), lenS, freqS, 0);
		pt.addStringCountFreq(T.c_str(), lenT, freqT, lenS);

		long long ans = 0;
		reu(i, 2, pt.nNodes)
			ans += (long long)freqS[i] * freqT[i];

//		cout << ans << endl;

		ll naiveans = 0;
		map<string,int> cntT;
		rep(k, lenT) rer(l, k+1, lenT)
			++ cntT[T.substr(k, l-k)];
		rep(i, lenS) rer(j, i+1, lenS) {
			string a = S.substr(i, j-i);
			if(a == string(a.rbegin(), a.rend()))
				naiveans += cntT[a];
		}
		if(ans != naiveans)
			cerr << ans << " != " << naiveans << endl;
	}
	return 0;
}

int main() {
//	return test();

	bool capitalLetters[128] = {};
	rep(a, 26) capitalLetters['A' + a] = true;

	const int MaxLen = 500000;

	char *S = new char[MaxLen+1], *T = new char[MaxLen+1];
	int lenS = readString(S, 1, MaxLen, capitalLetters); readEOL();
	int lenT = readString(T, 1, MaxLen, capitalLetters); readEOL();
	assert(getchar() == EOF);

	PalindromicTree pt;
	pt.init(lenS + lenT);
	vector<int> freqS, freqT;
	pt.addStringCountFreq(S, lenS, freqS, 0);
	pt.addStringCountFreq(T, lenT, freqT, lenS);

	long long ans = 0;
	reu(i, 2, pt.nNodes)
		ans += (long long)freqS[i] * freqT[i];
	printf("%lld\n", ans);
	return 0;
}
0