結果

問題 No.263 Common Palindromes Extra
ユーザー kriiikriii
提出日時 2019-08-24 21:42:51
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 242 ms / 2,000 ms
コード長 1,727 bytes
コンパイル時間 785 ms
コンパイル使用メモリ 72,820 KB
実行使用メモリ 150,248 KB
最終ジャッジ日時 2024-04-22 14:04:09
合計ジャッジ時間 2,817 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 9 ms
5,376 KB
testcase_04 AC 35 ms
6,044 KB
testcase_05 AC 34 ms
5,376 KB
testcase_06 AC 6 ms
5,376 KB
testcase_07 AC 142 ms
99,680 KB
testcase_08 AC 134 ms
99,680 KB
testcase_09 AC 242 ms
150,248 KB
testcase_10 AC 173 ms
150,132 KB
testcase_11 AC 31 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct eertree{
	eertree(string &s){
		push(s);
	}

	struct node{
		int nxt[26] = { 0, };
		int len = 0, suf = 0, occur = 0;
	};
	vector<node> trie;
	int size, maxSuf;

	void push(string &str){
		trie.clear();
		trie.resize(3);
		size = 2;
		trie[1].len = -1, trie[1].suf = 1;
		trie[2].len = +0, trie[2].suf = 1;
		maxSuf = 2;

		for (int pos = 0; pos < str.length(); pos++)
		{
			int cur = maxSuf, len = 0, sym = str[pos] - 'A';

			while (1){
				len = trie[cur].len;
				if (pos - len - 1 >= 0 && str[pos - len - 1] == str[pos]) break;
				cur = trie[cur].suf;
			}

			if (trie[cur].nxt[sym]){
				maxSuf = trie[cur].nxt[sym];
			}
			else{
				maxSuf = ++size;
				trie.push_back(node());
				trie[size].len = trie[cur].len + 2;
				trie[cur].nxt[sym] = size;

				if (trie[size].len == 1){
					trie[size].suf = 2;
				}
				else{
					while (1){
						cur = trie[cur].suf;
						len = trie[cur].len;
						if (pos - len - 1 >= 0 && str[pos - len - 1] == str[pos]){
							trie[size].suf = trie[cur].nxt[sym];
							break;
						}
					}
				}
			}

			trie[maxSuf].occur++;
		}

		for (int i = size; i >= 3; i--){
			int suf = trie[i].suf;
			if (suf >= 3){
				trie[suf].occur += trie[i].occur;
			}
		}
	}
};

long long inter(eertree& a, eertree& b, int i, int j)
{
	long long res = (long long)a.trie[i].occur * b.trie[j].occur;
	for (int sym = 0; sym < 26; sym++){
		int nxtI = a.trie[i].nxt[sym];
		int nxtJ = b.trie[j].nxt[sym];
		if (nxtI && nxtJ){
			res += inter(a, b, nxtI, nxtJ);
		}
	}
	return res;
}

int main()
{
	string s, t;
	cin >> s >> t;

	eertree p(s), q(t);
	cout << inter(p, q, 1, 1) + inter(p, q, 2, 2);

	return 0;
}
0