yukicoder-465

从 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/465 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP] ==

=== Description ===

{{{
#!html
<p>给定一个字符串$S$，问四元组$(P_1,P_2,A,P_3)$的方案数，其中$S=P_1+P_2+A+P_3$，并且$P_1,P_2,P_3$是$3$个非空回文串，$A$是任意一个非空字符串。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">$S$</p>
<p>
$4 \le |S| \le 500000$，$S$仅包含英文小写字母。
</p>
}}}

=== Output ===

{{{
#!html
<p>输出四元组的个数</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
testsetlevelisminim
</pre>
}}}
输出
{{{
#!html
<pre>
8
</pre>

<p>
总共有下面$8$个四元组。
<ul>
<li>(t, e, stsetlevelis, minim)</li>
<li>(t, e, stsetlevelismini, m)</li>
<li>(t, estse, tlevelis, minim)</li>
<li>(t, estse, tlevelismini, m)</li>
<li>(testset, l, evelis, minim)</li>
<li>(testset, l, evelismini, m)</li>
<li>(testset, level, is, minim)</li>
<li>(testset, level, ismini, m)</li>
</ul>
</p>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
xxoxxxxoxxoxxoxxxxoxxxxoxxxxoxxoxxoxxxxoxx
</pre>
}}}
输出
{{{
#!html
<pre>
92
</pre>
}}}

==== Sample 3 ====
输入
{{{
#!html
<pre>
ppppppppppppppppapppppppp
</pre>
}}}
输出
{{{
#!html
<pre>
1009
</pre>
}}}

No.465 PPPPPPPPPPPPPPPPAPPPPPPPP

Description

给定一个字符串$S$，问四元组$(P_1,P_2,A,P_3)$的方案数，其中$S=P_1+P_2+A+P_3$，并且$P_1,P_2,P_3$是$3$个非空回文串，$A$是任意一个非空字符串。

Input

$S$

$4 \le |S| \le 500000$，$S$仅包含英文小写字母。

Output

输出四元组的个数

Sample

Sample 1

输入

testsetlevelisminim

输出

总共有下面$8$个四元组。

(t, e, stsetlevelis, minim)
(t, e, stsetlevelismini, m)
(t, estse, tlevelis, minim)
(t, estse, tlevelismini, m)
(testset, l, evelis, minim)
(testset, l, evelismini, m)
(testset, level, is, minim)
(testset, level, ismini, m)

Sample 2

输入

xxoxxxxoxxoxxoxxxxoxxxxoxxxxoxxoxxoxxxxoxx

输出

Sample 3

输入

ppppppppppppppppapppppppp

输出