use std::collections::*; type Map = BTreeMap; fn main() { input!(s: chars, t: chars); let mut tree = PalindromicTree::new(); let mut a = vec![]; for s in s { a.push(tree.add(s)); } tree.add('$'); tree.add('@'); let mut b = vec![]; for t in t { b.push(tree.add(t)); } let tree = tree; let hist = |a: Vec| -> Vec { let mut cnt = vec![0; tree.node.len()]; for p in a.iter() { cnt[*p] += 1; } for i in (2..cnt.len()).rev() { cnt[tree.node[i].fail()] += cnt[i]; } cnt }; let a = hist(a); let b = hist(b); let ans = a.into_iter().zip(b).skip(2).fold(0, |s, p| s + p.0 * p.1); println!("{}", ans); } #[derive(Debug)] struct Node { fail: u32, len: u32, next: Map, } impl Node where T: Copy + Ord, { fn new(fail: usize, len: usize) -> Self { Self { fail: fail as u32, len: len as u32, next: Map::new(), } } fn next(&self, x: T) -> Option { self.next.get(&x).map(|p| *p as usize) } fn insert(&mut self, c: T, x: usize) { self.next.insert(c, x as u32); } fn fail(&self) -> usize { self.fail as usize } fn len(&self) -> usize { self.len as usize } } pub struct PalindromicTree { s: Vec, pos: Vec, node: Vec>, } impl PalindromicTree where T: Copy + Ord, { pub fn new() -> Self { Self { s: vec![], pos: vec![], node: vec![Node::new(0, !0), Node::new(0, 0)], } } pub fn add(&mut self, c: T) -> usize { self.s.push(c); let all = self.s.len(); let now = self.pos.last().map_or(1, |p| *p); let mut x = now; while x > 0 { let k = self.node[x].len(); if k + 2 <= all && self.s[all - k - 2] == c { break; } x = self.node[x].fail(); } let len = self.node[x].len() + 2; let mut fail = 1; if x > 0 { fail = self.node[now].fail(); while fail > 0 { let k = self.node[fail].len(); if self.node[fail].next(c).is_some() && self.s[all - k - 2] == c { break; } fail = self.node[fail].fail(); } fail = self.node[fail].next(c).unwrap(); } if let Some(z) = self.node[x].next(c) { self.pos.push(z); } else { let y = self.node.len(); self.node[x].insert(c, y); self.node.push(Node::new(fail, len)); self.pos.push(y); } self.pos.last().cloned().unwrap() } } /* impl PalindromicTree where T: std::fmt::Debug, { pub fn enumerate(&self, x: usize) { println!("enumerate: {}", x); let mut pos = self.pos[x]; while pos > 1 { let len = self.node[pos].len; println!("{:?}", &self.s[(x - len + 1)..=x]); pos = self.node[pos].fail; } } } */ // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ----------