#1625. [语言月赛 202309] 真的没有 idea 啦

[语言月赛 202309] 真的没有 idea 啦

题目描述

给定一个字符串 ss 和一个字符串 tt,请你求出:ss 有多少对前缀后缀对 (x,y)(x, y),使得 yxyx 等于 tt。

形式化的,设 nn 是字符串 ss 的长度,你要求出有多少对 (i,j)(i, j) 满足 1≤i,j≤n1 \leq i, j \leq n 使得 sjsj+1…sns1s2…si=ts_{j}s_{j+1}\dots s_ns_1s_2\dots s_i = t。

其中 sis_i 表示 ss 的第 ii 个字符,字符串下标从 11 开始。

输入格式

本题单个测试点内有多组测试数据。输入的第一行是一个整数,表示数据组数 TT。

对每组数据,按如下格式输入:
第一行是一个字符串,表示 ss。
第二行是一个字符串,表示 tt。

输出格式

对每组数据,输出一行一个整数表示答案。

样例

1
aabaabaabaab
aabaabaab
2

题目来源:洛谷 B3859