Problem2938--后缀数组+回文自动机+manacher+kmp

2938: 后缀数组+回文自动机+manacher+kmp

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 31  Solved: 6
[Submit] [Status] [Web Board] [Creator:]

Description

先有一个字符串s,我们定义一个好的子串:str1 + str2 + str1组成,并且|str1| >= k && |str2| >= 1
ps:当字符串相同,但是位置不同的时候,我们把他们算为两个好的子串。 位置相同,但拆分不同的子串算同一子串 


Input

第一行一个字符串s (1 <= |s| <= 1e4 + 5e3)
下一行输入一个数字k (1 <= k <= 100)

Output

输出一个数字,代表着s中有多少个好的子串个数

Sample Input Copy

ababca
1

Sample Output Copy

4

HINT

好的子串分别为:
aba
bab
abca
ababca