本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1131. 【KMP】似乎在梦中见过的样子


Description

「Madoka,不要相信QB!」伴随着Homura的失望地喊叫,Madoka与QB签订了契约。
这是Modoka的一个噩梦,也同时是上个轮回中所发生的事。为了使这一次Madoka不再与QB签订契约,Homura决定在刚到学校的第一天就解决QB。然而,QB也是有许多替身的(但在第八话中的剧情显示它也有可能是无限重生的),不过,意志坚定的Homura是不会放弃的——她决定消灭所有可能是QB的东西。现在,她已感受到附近的状态,并且把它转化为一个长度为n的字符串交给了学OI的你。
现在你从她的话中知道,所有形似于A+B+A的字串都是QB或它的替身,且∣A∣≥k,∣B∣≥1(位置不同其他性质相同的子串算不同子串,位置相同但拆分不同的子串算同一子串),然后你必须尽快告诉Homura这个答案——QB以及它的替身的数量。
注:对于一个字符串S,|S|表示S的长度。

Input

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

Output

仅一行一个数ans,表示QB以及它的替身的数量。

Samples

Input Copy
aaaaa
1
Output
6

Hint

对于全部数据,1≤∣S∣≤1.5×104,1≤k≤100,且字符集为所有小写字母。

Source

信息学奥赛一本通·提高篇
Problem Information

Time Limit: 2000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
My history solutions

You didn't submit any solution!
Submit your solution

Login Register