前置概念
Border:如果字符串同长度的前缀与后缀相同,称该前缀(后缀)是一个Border(可以指这个前缀也可以指这个前缀的长度)
循环周期:对于字符串S和正整数p,如果有Si=Si−p,对于p<i≤|S|成立,称p是S的一个循环周期
循环节:若字符串S的周期p满足p∣|S|,称p是S的一个循环节
重要性质1:p是S的周期⇔|S|−p是S的Border
因此求Border问题与求周期问题等价
重要性质2:S的Border的Border也是S的Border
因此求S的所有Border等价于求最大Border(求完最大Border变为子问题)
Next数组
nxti的值为prefixi的非平凡最大Border
记nxt1=0
考虑prefixi的非平凡最大Border,去掉最后一个字符,就是prefixi−1的非平凡最大Border
但反过来,prefixi−1的非平凡最大Border加上一个字符,不一定是prefixi的非平凡最大Border(Si与Snxti−1+1不一定相等)
因此想求nxti,需遍历prefixi−1的所有非平凡Border,结合重要性质2,发现这个过程等价于去遍历nxti−1,nxtnxti−1,⋯,0
从大到小遍历,如果某一个Border加上后一个字符满足相等,就可以及时break
求Next数组代码
void get_nxt()
{
nxt[1] = 0;
for (int i = 2; i <= m; ++i)
{
int j = i - 1;
while (j != 0)
{
if (t[i] == t[nxt[j] + 1])
{
nxt[i] = nxt[j] + 1;
break;
}
j = nxt[j];
}
}
}
求Next数组复杂度分析
考虑势能分析
如果nxti=nxti−1+1,势能增加1
否则势能会先减少到某个nxtj,然后有nxti=nxtj+1,在寻找nxtj的过程中,势能减少,每次至少减少1,寻找结束后势能加1
如果一直到j=0都没有找到满足的nxtj,说明nxti=0,势能清空
综上,势能总量为O(N),时间复杂度就是O(N),常数不超过2
KMP思想
Next数组记录了每个位置的前缀的非平凡最大Border信息
利用这个信息可以加速字符串匹配
先看暴力匹配为什么慢
for (int i = 1, j = 1; i <= n; )
{
if (s[i] == t[j])
++i, ++j;
else
i = (i - 1) - (j - 1) + 1 + 1, j = 1;
if (j == m + 1)
{
std::cout << (i - 1) - m + 1 << '\n';
i = i - m + 2, j = 1;
}
}
暴力匹配的时间瓶颈在于:当遇到匹配失败的字符时,i和j大量的回溯
KMP算法首先预处理出模式串t的Next数组,然后基于这样一个事实节约时间:当遇到匹配失败的字符,i指针不需要动,尝试让j回溯到prefixj−1所有Border的长度即可,非Border长度一定不会匹配的更“远”
“尝试让j回溯到prefixj−1所有Border的长度”这个过程,结合重要性质2和已经预处理好的Next数组,其实还是一个在Border链上跳的过程
结合势能分析,复杂度为O(N+M)
for (int i = 1, j = 1; i <= n; )
{
if (s[i] == t[j])
++i, ++j;
else // 遇到匹配失败的字符,在Border链上跳
while (j != 1 && s[i] != t[j])
j = nxt[j - 1] + 1;
if (j == 1 && s[i] != t[j]) // 如果到1了还是失败,说明这个位置不可能
++i;
if (j == m + 1)
{
std::cout << (i - 1) - (j - 1) + 1 << '\n';
j = nxt[m] + 1;
}
}
KMP模板
namespace KMP
{
const int N = 1e6 + 10;
int nxt[N];
std::string s, t;
int n, m;
void init(std::string a, std::string b)
{
s = "?" + a, t = "?" + b;
n = s.length() - 1, m = t.length() - 1;
std::fill(nxt + 1, nxt + m + 1, 0);
}
void get_nxt()
{
nxt[1] = 0;
for (int i = 2; i <= m; ++i)
{
int j = i - 1;
while (j != 0)
{
if (t[i] == t[nxt[j] + 1])
{
nxt[i] = nxt[j] + 1;
break;
}
j = nxt[j];
}
}
}
std::vector<int> get_start_pos(bool start_from_zero)
{
std::vector<int> res;
for (int i = 1, j = 1; i <= n; )
{
if (s[i] == t[j])
++i, ++j;
else
while (j != 1 && s[i] != t[j])
j = nxt[j - 1] + 1;
if (j == 1 && s[i] != t[j])
++i;
if (j == m + 1)
{
res.push_back((i - 1) - (j - 1) + 1 + (start_from_zero ? -1 : 0));
j = nxt[m] + 1;
}
}
return res;
}
}