yukicoder-263

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/263 No.263 Common Palindromes Extra] ==

=== Description ===

{{{
#!html
<p>给出字符串$S$和$T$，求满足以下条件的四元组$(i,j,k,l)$的个数。$U[x,y]$表示字符串$U$从$x$开始到$y$结束的连续子串。
<ul>
<li>$1 \le i \le j \le |S|$</li>
<li>$1 \le k \le l \le |T|$</li>
<li>$S[i,j]=T[k,l]$</li>
<li>$S[i,j]$是回文串</li>
</ul>
</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$S$<br>
$T$
</p>

<p>$1 \le |S|, |T| \le 500000$，$S$和$T$仅包含英文大写字符，保证答案不会超过$10^{18}$。</p>
}}}

=== Output ===

{{{
#!html
<p>输出满足条件的四元组个数。</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
AABA
BAAB
</pre>
}}}
输出
{{{
#!html
<pre>
9
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
USAGI
MYON
</pre>
}}}
输出
{{{
#!html
<pre>
0
</pre>
}}}

No.263 Common Palindromes Extra

Description

给出字符串$S$和$T$，求满足以下条件的四元组$(i,j,k,l)$的个数。$U[x,y]$表示字符串$U$从$x$开始到$y$结束的连续子串。

• $1 \le i \le j \le |S|$
• $1 \le k \le l \le |T|$
• $S[i,j]=T[k,l]$
• $S[i,j]$是回文串

Input

$S$
$T$

$1 \le |S|, |T| \le 500000$，$S$和$T$仅包含英文大写字符，保证答案不会超过$10^{18}$。

Output

输出满足条件的四元组个数。

Sample

Sample 1

输入

AABABAAB

输出

9

Sample 2

输入

USAGIMYON

输出

0