回文字D
题目链接:nowcoder 217311
到主站看:https://blog.csdn.net/weixin_43346722/article/details/116244038
题目大意
定义一个 D 型回文串是指它的长度小于 D 或者它每个长度为 D 的子串都是回文串。
给你一个字符串,问你最少可以把它分割成多少个字符串,使得分割出的每个字符串都是 D 型回文串。
思路
这道题我们首先要搞清楚一个东西,如果 A 是 D 型回文串,然后在后面放一个字符 a,如果 A 的最后 D-1 个字符和 a 组合起来的字符串是回文串,那把 a 拼到 A 后面,它还是一个 D 型回文串。
那就有想法了,还是贪心的感觉,这个 D 型回文串能继续往后延伸就延伸,不能就跳到这个 D 型回文串的下一个字符开始继续。
然后最后你弄出多少个回文串,就是多少了。
由于这个是要判断一个字符串是否是回文串,那马拉车用不了,我们可以用哈希。
代码
#include<cstdio> #define ull unsigned long long using namespace std; int n, D, l, ans; ull lef[10000001], rig[10000001], d[10000001]; char c[10000001]; bool ck(int l, int r) {//哈希判断一个字符串是否是回文串 if (lef[r] - lef[l - 1] * d[r - l + 1] == rig[n - l + 1] - rig[n - r] * d[r - l + 1]) return 1; return 0; } int main() { scanf("%d %d", &n, &D); scanf("%s", c + 1); lef[0] = rig[0] = d[0] = 1; for (int i = 1; i <= n; i++) {//哈希预处理 d[i] = d[i - 1] * 131; lef[i] = lef[i - 1] * 131 + c[i] - 'a' + 1; rig[i] = rig[i - 1] * 131 + c[n - i + 1] - 'a' + 1; } l = 1; while (l <= n) { while (l + D - 1 <= n && ck(l, l + D - 1)) l++;//这个 D 型回文串可以继续往后延伸就一直延伸 l = l + D - 1;//跳到下一个的开始 ans++; } printf("%d", ans); return 0; }