UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4480. [Jsoi2013]快乐的jyy

统计 下载数据

Description

【故事背景】
JYY在JSOI有很多很多的好朋友,比如PUPPY,KFC还有PUPPUP。因为
有了这么多的好朋友,所以JYY每天都很快乐。某天,JYY发现好朋友之间关
系的好坏和名字有很大的关系,比如PUPPY和PUPPUP的关系就特别好,但是
和KFC的关系就很一般。JYY苦思冥想终于发现了其中的规律,现在JYY想知
道两个朋友之间关系的好坏,你能帮助JYY么?
【问题描述】
给定两个字符串A和B,表示JYY的两个朋友的名字。我们用A(i,j)表示A
字符串中从第i个字母到第j个字母所组成的子串。同样的,我们也可以定义B(x,y)。
JYY发现两个朋友关系的紧密程度,等于同时满足如下条件的四元组(i,j,x,y)
的个数:
1:1<=i<=j<=|A|
2:1<=x<=y<=|B|
3:A(i,j)=B(x,y)
4:A(i,j)是回文串
这里表示字符串A的长度。
JYY希望你帮助他计算出这两个朋友之间关系的紧密程度。

Input

数据包行两行由大写字母组成的字符串A和B
1≤|A|,|B|≤50000。

Output

包含一行一个整数,表示紧密程度,也就是满足要求的4元组个数

Sample Input

PUPPY
PUPPUP

Sample Output

17

Hint

Source

By 佚名上传