2023年7月20日发(作者：)

[dp][kmp]怪盗基德的挑战书HDU4552Problem Description　　“在树最美丽的那天，当时间⽼⼈再次把⼤钟平均分开时，我会降临在灯⽕之城的⾦字塔前，带⾛那最珍贵的笑容。”这是怪盗基德盗取巴黎卢浮宫的《蒙娜丽莎的微笑》这幅画时，挑战书上的内容。　　但这次，怪盗基德的挑战书上出现了⼀串串⼩写字母“”。柯南以⼩学⽣的眼睛，超凡⾼中⽣的头脑，快速统计各种字母频率，字符串长度，并结合挑战书出现的时间等信息，试图分析怪盗基德的意图。最后，他将线索锁定在字符串的循环次数上。并且进⼀步推理发现，从字符串的第⼀位开始，到第i位，形成该字符串的⼦串(c1, c2, c3 ... ci )。对于某⼀⼦串ci在该字符串中出现的次数记为ki，则全部⼦串的循环次数总和AIM = k1 + k2 + ... + ki + ... + kn，柯南发现，AIM恰好对应⼀个ASCII码！所以，只要把挑战书上的字符串转变成数字，再找到对应的ASCII码，就可以破解这份挑战书了！　　现在，你的任务就是把字符串转变成对应数字，因为ASCII码以及扩展ASCII码全部只有256个，所以，本题只要把结果对256取余即可。Input输⼊有多组测试数据；每组测试数据只有⼀个字符串，由各种⼩写字母组成，中间⽆空格。字符串的长度为L(0 < L <= 100000)。Output请计算并输出字符串的AIM值，每组数据输出⼀⾏。Sample Inputaaa

ababSample Output6

6题意： 给出⼀个字符串，求出所有前缀出现次数之和。分析： 思路很好想，就是dp+next数组，然后把每个dp加和取模即可，之前博客()写过，不过多解释。具体代码如下：8293637#include #include #include #include #include #define mod 256using namespace std;//类似之前训练的原题，只需要求出前缀出现的次数，dp+next数组解决

char s[100005];int _next[100005], dp[100005];

signed main(){ while(~scanf("%s", s+1)) { int len = strlen(s+1); for(int i = 2, j = 0; i <= len; i++) { while(j && s[j+1] != s[i]) j = _next[j]; if(s[j+1] == s[i]) j++; _next[i] = j; } for(int i = 1; i <= len; i++) dp[i] = 1; for(int i = len; i >= 1; i--) dp[_next[i]] += dp[i];

int ans = 0;

for(int i = 1; i <= len; i++) ans = (ans+dp[i])%mod; printf("%dn", ans); } return 0;}