from collections import defaultdict MOD = (1<<61) - 1 BASE = 10007 MAXN = 10**6 POWER = [1] for i in range(1, MAXN+1): POWER.append((POWER[-1] * BASE) % MOD) class RollingHash: def __init__(self, string): self.string = string self.size = len(string) # construct self.hashed = [0] for i in range(self.size): self.hashed.append(self.hashed[-1] * BASE + ord(self.string[i])) self.hashed[-1] %= MOD def query(self, l, r): assert 0 <= l <= r <= self.size return (self.hashed[r] - self.hashed[l] * POWER[r-l]) % MOD def composite_query(R1, R2, l1, r1, l2, r2): LEFT = R1.query(l1, r1) RIGHT = R2.query(l2, r2) return (RIGHT + LEFT * POWER[r2-l2]) % MOD class eertree: def __init__(self, string): self.string = string self.size = len(string) self.r1 = RollingHash(self.string) self.r2 = RollingHash(''.join(reversed(self.string))) def __rev(self, l, r): return self.size - r, self.size - l def build(self): BEGIN = ord('A') # or ord('a') # Centroid of the palindrome A-Z and '' ptr = [defaultdict(lambda: -2) for _ in range(27)] lazy = [defaultdict(int) for _ in range(27)] tail = [(-1, -1) for _ in range(27)] tail[26] = (0, 0) ptr[26][0] = -1 for i in range(self.size): # Centroid = self.string[i] ok, ng = -1, min(i, self.size-i-1)+1 ID = ord(self.string[i]) - BEGIN while ng - ok > 1: x = (ng + ok) >> 1 h = self.r1.query(i+1, i+1+x) if ptr[ID][h] >= -1: ok = x else: ng = x if ok == -1: ptr[ID][0] = -1 ok = 0 prh = self.r1.query(i+1, i+1+ok) longest = ok for j in range(ok+1, min(i, self.size-i-1)+1): l1, r1 = i+1, i+1+j l2, r2 = self.__rev(i-j, i) h1 = self.r1.query(l1, r1) h2 = self.r2.query(l2, r2) if h1 == h2: longest = j ptr[ID][h1] = prh prh = h1 else: break lazy[ID][prh] += 1 tail[ID] = max(tail[ID], (longest, prh)) # Centroid = '' ok, ng = 0, min(i, self.size-i-1) + 1 ID = 26 while ng - ok > 1: x = (ng + ok) >> 1 h = self.r1.query(i, i + x) if ptr[ID][h] >= -1: ok = x else: ng = x prh = self.r1.query(i, i+ok) longest = ok for j in range(ok+1, min(i, self.size-i)+1): l1, r1 = i, i + j l2, r2 = self.__rev(i - j, i) h1 = self.r1.query(l1, r1) h2 = self.r2.query(l2, r2) if h1 == h2: longest = j ptr[ID][h1] = prh prh = h1 else: break lazy[ID][prh] += 1 tail[ID] = max(tail[ID], (longest, prh)) for ID in range(27): _, v = tail[ID] while v > 0: par = ptr[ID][v] lazy[ID][par] += lazy[ID][v] v = par lazy[26][0] = 0 return lazy s = input() t = input() palS = eertree(s) palT = eertree(t) ResultS = palS.build() ResultT = palT.build() ans = 0 for ID in range(27): for h in ResultS[ID]: ans += ResultS[ID][h] * ResultT[ID][h] print(ans)