Time Limit: 2s Memory Limit: 256MB

题目描述

众所周知,江安掌上农业技术交流群严禁复读行为,然鹅睿智的复读机们不但肆意践踏群规,搞得群里乌烟瘴气, 甚至还图谋拿群规当挡箭牌,公然在复读时加上一些奇怪的东西,妄想逃避禁言的正道直行。其气焰之嚣张,行径之恶劣,令人发指。

mUv7q0.png

现在前群主拿着江安掌上农业技术交流群的聊天记录找到了你,告诉你这是后缀自动机的模板题,希望你能帮忙找到其中的间隔复读行为的次数,以此决定下一位幸运群友的禁言时间。

具体来说,前群主给了你一个长度为\(n\)的字符串,表示群里聊天记录的拼接,你需要找到其中形如\(A+B+A\)的子串的数量。在这里,我们认为,同位置子串的不同分割只需要计数一次,但位置不同而内容一致的子串需要分别计数(样例解释中提供了更详细的例子)。

此外,为了尽量避免无辜群友风评被害,前群主希望你找到的形如\(A+B+A\)的子串中,\("A"\)的长度必须大于等于输入的\(k\),\("B"\)的长度必须大于等于\(1\)(样例解释中提供了更详细的例子)。

INPUT

第一行输入一个整数\(T\),表示数据组数。 每组数据输入两行,第一行输入一个仅由小写字母构成的字符串\(S\),第二行输入一个整数\(k\),表示在你寻找间隔复读行为时的至少的长度,具体可以参考样例解释。

\(1\le T \le 10,1\le |S|\le 3000,1\le k\le 10\),另外保证std不超过25行并且没有用后缀自动机,保证输入数据没有刻意构造卡哈希。

OUTPUT

输出一个数字 , 表示间隔复读行为的次数 。

SAMPLE INPUT 1

1 
aaaaa 
1

SAMPLE OUTPUT 1

6

SAMPLE INPUT 2

1
abcabcabc
2

SAMPLE OUTPUT 2

8

HINT

第一组:\(aaaaa\)中,\((1,3),(2,4),(3,5),(1,4),(2,5),(1,5)\)都是形如\(A+B+A\)的子串,且\(A\ge k=1,B\ge 1\)。

注意,以\((1,5)\)为例,尽管\(aaaaa\)有两种形如\(A+B+A\)的分割方式\((a+aaa+a与aa+a+aa)\),但在计数时我们只考虑一次。

第二组: \(abcabcabc\)中,\((1,5),(2,6),(3,7),(4,8),(5,9),(1,8),(2,9),(1,9)\)都是形如\(A+B+A\)的子串,且\(A\ge k=2\),\(B\ge 1\)。

以\((1,4)\)为例,虽然\((1,4)\)满足\(A+B+A\)的形式,即\("a+bc+a"\),但由于其中\(A\)即\("a"\)的长度不满足大于等于\(2\),所以\((1,4)\)不是合法的方案。

注意,以\((1,5)\)与\((4,8)\)为例,尽管两者都为\("abcab"\),但由于两者出现的位置不同,在计数时我们需要分别考虑。

由于数据范围不太大 , 可以尝试使用相对暴力的思路