[题解] HDU 3336. KMP算法 / 字符串题经典 DP
TAG: KMP, next数组, 动态规划
题目链接: 点击此处打开题目
题目大意
给定一个全由小写字母组成的长度为 \(n\) 的字符串，找出它的所有非空前缀，并计算这些前缀在整个字符串中总共匹配了多少次。结果对 10007 取模。
核心思路
这题要求我们在整个串里找所有前缀的出现次数总和。一看是关于前缀的匹配，脑海中立刻就要反应出 KMP 算法的 next 数组（或称 fail 指针）。
在 KMP 中，next[i] 的含义是：以第 i 个字符结尾的子串，与原串前缀能匹配的最长长度。
举个例子，如果 next[i] = j，说明原串中长度为 j 的前缀，刚好和以 i 结尾的后缀一模一样。这就是一次前缀匹配！
不仅如此，前缀内部可能还有更短的匹配，即 next[next[i]] 这个长度的前缀同样在位置 i 完成了匹配。
如果对于每个位置 i 我们都顺着 next 指针暴力往回跳去数次数，极限情况下会被卡成 \(O(n^2)\)。
所以我们需要借助动态规划（DP）的思想来把统计过程优化到 \(O(n)\)：
我们发现，在位置 i 能匹配上的前缀数量，完全等价于它能通过 next[i] 跳到的那个位置能匹配上的前缀数量，再加上当前这个最长公共前后缀本身（以及单个字符前缀情况，等效为 +1）。
复杂度分析
- 时间复杂度: \(O(N)\)。KMP 求解
next数组是线性的，后续的 DP 一重循环也是线性的。 - 空间复杂度: \(O(N)\)。使用了一个
nxt数组和一个状态数组dp，大小在 \(2 \times 10^5\) 级别，完全开得下。
原理解析与 AC 代码
在看代码前，明确以下核心变量的含义：
nxt[i]：标准的 KMP next 数组，代表以i为结尾的前缀字符串 的最长公共前后缀长度（注意代码里做了 1-based 偏移，即字符串加了空格）。dp[i]：表示以原字符串的第i个字符结尾的子串中，总共包含了多少个该字符串的前缀。- 核心转移方程：
\[dp[i] = dp[nxt[i]] + 1
\]
（意思就是，继承通过 nxt[i] 指向的那个前缀的包含次数，再加上当前长度自身算作的1次前缀）。
以下是 AC 代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int mod=10007;
const int N=2e5+5;
int nxt[N];
int ls,n;
int dp[N];//f[i]:表示以位置i结尾的前缀个数
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while(t--){cin>>n;string s;cin>>s;s=" "+s;nxt[1]=0;for(int i=2,j=0;i<=n;i++){while(j&&s[i]!=s[j+1]) j=nxt[j];if(s[i]==s[j+1]) j++;nxt[i]=j;}int ans=0;for(int i=1;i<=n;i++){dp[i]=(dp[nxt[i]]+1)%mod; // 核心状态转移ans=(ans+dp[i])%mod; // 累加所有位置贡献，边加边取模}cout<<ans<<endl;}return 0;
}