|
试题描述
|
|
「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<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> 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<n;i++){//正常的处理出nxt数组 j=p[i]; while(j>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<n;i++){//枚举右端点 while(j>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; }