NC217311. 回文字D
描述
死宅hx特别喜欢《头文字D》这部动漫，“逮虾户”神曲是他刷题和比赛时的必听曲目之一。因此，hx发明了一种型回文串。假如字符串长度为
，若满足以下两个条件之一，该字符串就为
型回文串。
1：假如，则该字符串为
型回文串（并不要求这个字符串为回文串）。
2：假如，且该字符串中任意一个长度为
的子串均为回文串，则该字符串为
型回文串。
定义字符串的拼接操作符为，
表示将字符串
接到
后面，例如
。现给你一个长度为
且均为小写字母的字符串
，你可以任意划分
，使得
。在满足
均为
型回文串的条件下，请你告诉hx最小的
是多少。
输入描述
第一行两个正整数
,
，其中
,
。
第二行一个长度为
。
输出描述
输出最小的
。
示例1
输入:
4 2 aabb
输出:
2
C++(clang++11) 解法, 执行用时: 241ms, 内存消耗: 254884K, 提交时间: 2021-04-03 13:46:11
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
char s[N];
typedef unsigned long long ull;
ull hs[N],ts[N],pw[N];
ull bs=31;
#define to(x) ((x)-'a'+1)
int main(){
int n,d;
scanf("%d%d%s",&n,&d,s+1);
pw[0]=1;
for(int i=1;i<=n;++i){
pw[i]=pw[i-1]*bs;
hs[i]=hs[i-1]*bs+to(s[i]);
}
for(int i=n;i>0;--i){
ts[i]=ts[i+1]*bs+to(s[i]);
}
int j,ans=0;
for(int i=1;i<=n;i=j){
j=i+d-1;
while(j<=n&&(hs[j]-hs[i-1]*pw[d])==ts[i]-ts[j+1]*pw[d]){
++j;
++i;
}
++ans;
}
printf("%d",ans);
return 0;
}