結果

問題 No.263 Common Palindromes Extra
ユーザー koba-e964koba-e964
提出日時 2021-12-31 02:02:34
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,607 bytes
コンパイル時間 3,293 ms
コンパイル使用メモリ 164,384 KB
実行使用メモリ 77,760 KB
最終ジャッジ日時 2024-10-07 06:24:26
合計ジャッジ時間 5,355 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 25 ms
74,220 KB
testcase_01 AC 22 ms
73,968 KB
testcase_02 AC 22 ms
73,980 KB
testcase_03 AC 29 ms
74,628 KB
testcase_04 AC 62 ms
77,760 KB
testcase_05 AC 57 ms
77,500 KB
testcase_06 AC 26 ms
74,204 KB
testcase_07 AC 69 ms
77,760 KB
testcase_08 AC 63 ms
77,500 KB
testcase_09 AC 81 ms
77,628 KB
testcase_10 RE -
testcase_11 AC 55 ms
77,508 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3683474#1, modified
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 500010

enum Type{
	S,
	T,
};

struct Node{
	    int parent_id,children[28],suffix_link,length,count;
};

int num_nodes,root,last_node;
ll dp[2][NUM];
char base_ch;
Node nodes[NUM];
string input_S,input_T,line;


void add(int loc){

	char tmp_ch = line[loc];

	int tmp_node = last_node;

	while(true){
		if(loc-1-nodes[tmp_node].length >= 0 && line[loc-1-nodes[tmp_node].length] == tmp_ch){
			break;
		}
		tmp_node = nodes[tmp_node].suffix_link;
	}

	if(nodes[tmp_node].children[tmp_ch-base_ch] > 0){

		last_node = nodes[tmp_node].children[tmp_ch-base_ch];
		nodes[last_node].count++;
		return;
	}

	last_node = num_nodes++;
	nodes[tmp_node].children[tmp_ch-base_ch] = last_node;

	nodes[last_node].length = nodes[tmp_node].length+2;
	nodes[last_node].parent_id = tmp_node;
	nodes[last_node].count = 1;

	if(nodes[last_node].length == 1){

		nodes[last_node].suffix_link = root+1;

	}else{

		while(true){
			tmp_node = nodes[tmp_node].suffix_link;
			if(loc-1-nodes[tmp_node].length >= 0 && line[loc-1-nodes[tmp_node].length] == tmp_ch){

				nodes[last_node].suffix_link = nodes[tmp_node].children[tmp_ch-base_ch];
				break;
			}
		}
	}
}

int get_index(){

	return last_node;
}

void init(string arg_line){

	line = arg_line;
	num_nodes = 0;

	base_ch = '?';

	root = 0;
	nodes[root].suffix_link = -1;

	for(int i = 0; i < NUM; i++){

		nodes[i].parent_id = -1;
		nodes[i].count = 0;

		for(int k = 0; k < 28; k++){
			nodes[i].children[k] = -1;
		}
	}

	num_nodes = 2;
	last_node = root;

	nodes[root].length = -1;
	nodes[root+1].length = 0;

	nodes[root].suffix_link = root;
	nodes[root+1].suffix_link = root;

	nodes[root].parent_id = -1;
	nodes[root+1].parent_id = root;
}

int main(){

	cin >> input_S >> input_T;

	string LINE = input_S + "?@" + input_T;

	init(LINE);

	int tmp_index;

	for(int i = 0; i < 2; i++){
		for(int k = 0; k < NUM; k++){

			dp[i][k] = 0;
		}
	}

	for(int i = 0; i < LINE.length(); i++){

		add(i);
		tmp_index = get_index();

		if(i < input_S.length()){

			dp[S][tmp_index]++;

		}else if(i >= input_S.length()+2){

			dp[T][tmp_index]++;
		}
	}

	ll ans = 0;

	for(int i = num_nodes-1; i >= 2; i--){

		ans += dp[S][i]*dp[T][i];
		dp[S][nodes[i].suffix_link] += dp[S][i];
		dp[T][nodes[i].suffix_link] += dp[T][i];
	}

	printf("%lld\n",ans);

    return 0;
}
0