字符串算法
参考: Bilibili
T为文本串(被匹配), P为模式串(进行匹配的串)
真前缀: 前缀但不包含整个字符串
真后缀同理
kmp算法
KMP算法考虑T的每个前缀的每个后缀和P的前缀匹配
定义一个函数ne(i), 表示能作为P的第i个前缀的真后缀的P的最长前缀的长度(真前缀=真后缀), 举例:
abaa: ne(4) = 1
a---
---a
ababa: ne(5) = 3
aba---
---aba
//m为模式串长度
for(int i = 1, j = 0; i <= m; i ++ )
{
while(j > 0 && t[i] != p[j + 1])
j = ne[j];
if(t[i] == p[j + 1]) j ++;
if(j == m)
{
//codes
j = ne[j];
}
}
ne函数求法
显然ne(1) = 0(必须是真后缀)
//n为文本串长度
ne[1] = 0;
for(int i = 2, j = 0; i <= n; i ++ )
{
while(p[i] != p[j + 1] && j > 0)
j = ne[j];
if(p[i] == p[j + 1]) j ++;
ne[i] = j;
}
时间复杂度\(O(n + m)\)
exkmp
参考: bilibili
数组下标从0开始编号
有时, 我们想知道T的每一个后缀与P的最长公共前缀
extend(i)
P与T[i, n-1]的最长公共前缀长度
人话：从文本串T的第i位开始, 模式串P与主串T的匹配字符个数/文本串的每一个后缀与模式串的前缀匹配数
例如
extend[1] = 3
extend[2] = 0
extend[3] = 3
extend[4] = 0
extend[5] = 1
extend[6] = 0
next(i)/Z函数
P与P[i, m-1]的最长公共前缀长度
从自己的第i位开始, 模式串P与自己匹配的字符个数
通俗的说: P对P求exkmp求出的就是next数组
假设图中已知next[1-5], 那么我们就可以用next[2]更新next[6], 用next[3]更新next[7]
图中圈出的部分也被称为Z-box, 用Z-box来加速更新
Z-box定义: 对于i, 我们称区间[i, i+next[i]-1]是i的匹配段, 也叫做Z-box
算法流程:
计算完前i-1个next, 维护盒子\([l, r]\), 则\(s[l, r] = s[1, r-l+1]\)
- 如果i < r(在盒内) \(s[i, r]=s[i-l+1,r-l+1]\)
- 若\(ne[i-l+1]<r-i+1\), 则ne[i]=r-i+1
- 若\(ne[i-l+1] \geq r-i+1\), 则令\(ne[i]=r-i+1\), 从r+1往后暴力枚举
- 如果\(i>r\)(在盒外), 则从i开始暴力枚举
- 求出ne[i]后, 如果\(i+ne[i]-1>r\), 则更新盒子\(l=i\), \(r=i+ne[i]-1\)
图示
- 在盒内且左边的对称点的长度不超过盒子，i的ne值与左边的ne值相同
比如下图
假如有了1-5的ne值, 算6的ne值, 发现对称点(2)的ne值不会超出盒子, 那么该点的ne值即为ne[2]
- 在盒内但左边的对称点的ne值的长度超出盒子, 先将ne顶到盒子最右端, 然后暴力匹配
比如下图
有了ne[1-2]之后, ne[3]肯定不为ne[2], 因为会超出盒子, 所以先把ne[3]顶到盒子最后, 然后暴力匹配出结果
- 不在盒内, 暴力匹配
如图
盒子为[2, 3], 计算ne[4], 这时只能暴力匹配
- 最后别忘了更新盒子
时间复杂度\(O(n)\)
void getnxt(char *s, int n)//n = strlen(s + 1)
{
ne[1] = n;
for(int i = 2, l, r = 0; i <= n; i ++ )
{
if(i <= r) ne[i] = min(ne[i - l + 1], r - i + 1);//盒内2种情况
while(s[1 + ne[i]] == s[i + ne[i]]) ne[i] ++;//暴戾枚举
if(i + ne[i] - 1 > r) l = i, r = i + ne[i] - 1;
}
}
//同理可以得到extend数组
void getextend(char *s, int n, char*t, int m)
{
for(int i = 1, l, r = 0; i <= m; i ++ )
{
if(i <= r) extend[i] = min(ne[i - l + 1], r - i + 1);
//条件中第三个条件即为暴力匹配
//前两个条件为不能越界
while(1 + extend[i] <= n && i + extend[i] <= m
&& s[1 + extend[i]] == t[i + extend[i]])
extend[i] ++;
//更新盒子
if(i + extend[i] - 1 > r) l = i, r = i + extend[i] - 1;
}
}