【例题4】子串拆分

题目描述

已知一个字符串$S$，求它有多少个形如$A + B + A$的子串（$len(A) \geq k$且$len(B) \geq 1$）。位置不同其他性质相同的子串算不同子串，位置相同但拆分不同的子串算同一子串。

输入格式

第一行一个字符串$S$，第二行一个数$k$。

输出格式

一个数，表示满足条件的子串数。

数据范围与提示

对于全部数据，$1 \leq |S| \leq 1.5 \times 10^4$，$1 \leq k \leq 100$，且字符集为所有小写字母。

样例

aaaaa
1

6

abcabcabc
2

8