试题描述

「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 的长度。

输入

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

输出

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

输入示例

样例输入 1

aaaaa

1

样例输入 2

abcabcabc

2

输出示例

样例输出 1

6

样例输出 2

8

其他说明

数据范围与提示

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

 

---

g感觉全世界都能过而我不能过，让老师改了三遍时间限制才卡过去，可能是因为我比被人都多用了一个循环的缘故

其实题目描述中有很明显的kmp的痕迹

“形如A+B+A”，脑子不好使的我以为是个回文结构，打算用住正反两边hash来写（字符串只会写hash  QAQ）

我们之所以会被卡时间，是因为用的方法是在太笨，枚举两个端点，然后判断是否成立

下面给出代码：（还是看注释吧）：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f;}inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ;}int p[15006],n,k;char s[15006];int ans=0;inline void kmp(int x){ int j=0; for(register int i=x;i<=n;i++) p[i]=x-1;//因为只处理x和之后的，所以从x开始就行了，生活所迫 for(register int i=x;i
            
             x-1&&s[j+1]!=s[i+1]) j=p[j]; if(s[j+1]==s[i+1]) j++; p[i+1]=j; } j=p[x]; for(register int i=x-1;i
             
              x-1&&s[j+1]!=s[i+1]) j=p[j]; if(s[j+1]==s[i+1]) j++; while((j-x+1)<<1>=(i+1-x+1)) j=p[j];//如果两个A的长度大于整个串，B就没了 if(j-x+1>=k) ans++;//A大于k就成立，答案加一 }}int main(){ scanf("%s",s+1); k=rd(); n=strlen(s+1); for(register int i=1;i<=n-k-k;i++) kmp(i);//每局左端点，因为|A|>=k，所以可以到n-k-k，都是生活所迫 write(ans); return 0;}