// https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3683474#1, modified #include 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; }