結果

問題 No.263 Common Palindromes Extra
ユーザー koba-e964koba-e964
提出日時 2021-12-31 02:04:28
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 2,499 bytes
コンパイル時間 3,994 ms
コンパイル使用メモリ 162,076 KB
実行使用メモリ 147,940 KB
最終ジャッジ日時 2024-10-07 06:25:59
合計ジャッジ時間 3,631 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
144,452 KB
testcase_01 AC 41 ms
144,256 KB
testcase_02 AC 43 ms
144,128 KB
testcase_03 AC 50 ms
144,944 KB
testcase_04 AC 82 ms
147,836 KB
testcase_05 AC 76 ms
147,940 KB
testcase_06 AC 44 ms
144,512 KB
testcase_07 AC 88 ms
147,836 KB
testcase_08 AC 83 ms
147,840 KB
testcase_09 AC 102 ms
147,940 KB
testcase_10 AC 110 ms
147,900 KB
testcase_11 AC 76 ms
147,840 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;
using namespace std;


#define NUM 1000010

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