kmp模板 & 最小表示法

发表于 | 更新于 | 分类于

KMP 模式匹配

时间复杂度：O(N + M)
求A是否为B的子串，并求出每次出现的匹配位置

1.求Next数组

对字符串A求自身匹配，求出Next数组，其中Next[i]表示A中以i为结尾(以i为后缀)的非前缀子串
与A的前缀能匹配的最大长度即：
Next[i] = max{j}, 其中i < j 且 a[i - j + 1 ~ i] = a[1 ~ j]
hint: 当不存在这样的j时 令Next[i] = 0;

步骤

  • 初始化Next[1] = j = 0, 假设Next[1 ~ i - 1]已求出，下面求解Next[i]
  • 利用前面的Next[1 ~ i - 1]进行状态转移，递推求Next[i])，不断尝试扩展匹配长度，
    如果扩展失败(下一个字符不相等)，令j = Nextj，
    直至j为0(应该从头开始重新匹配)
  • 如果能扩展成功，匹配长度j ++。 Next[i]的值就是j
1
2
3
4
5
6
7
8
9
10
11
12
char a[N], char b[M];		
int Next[N];		
void get_next()
{
    next[1] = 0;
    for(int i = 2, j = 0; i <= n; i ++ )
    {
        while(j > 0 && a[i] != a[j + 1])    j = Next[j];
        if(a[i] == a[j + 1])    j ++;
        Next[i] = j;
    }
}

2.求f[]匹配数组

类似于Next[]数组的求法, 当j == n时需要 j = Next[j], 此时要缩短匹配的长度,
因为a[j]已经匹配越界

1
2
3
4
5
6
7
8
9
10
void get_f()
{
    for(int i = 1, j = 0; i <= m; i ++ )
    {
        while(j > 0 && (j == n || b[i] != a[j + 1]))    j = Next[j];	//j == n a[]边界溢出的情况
        if(b[i] == a[j + 1])    j ++;
        f[i] = j;
        if(f[i] == n)   //即A在B中的某一次出现
    }
}

最小表示法

B[i]表示从i开始的循环同构字符串，即 s[i ~ n] + s[1 ~ i - 1]

算法概述:

求出一个字符串的旋转表示里的最小表示(将前缀接到后缀或后缀接到前缀)

思路详解

<

  1. 将字符串进行二倍扩展, 初始化i = 1, j = 2
  2. 通过直接向后扫描, 比较B[i] 与 b[j]两个循环同构串初始k - 0, k ++ 代表向后匹配
    1. k == n 则S只有一种字符构成, 任意B[i]都是最小表示
    2. 在 i + k处匹配失败
      若 s[i + k] > s[j + k] i += k + 1
      若 s[i + k] < s[j + k] j += k + 1
      若 i == j 则 i ++ 或 j ++ 即可
      3.i > n || j > n B[min(i, j)]即为最小表示, 否则重复第2步
      <
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[2 * n];		//二倍
int get_min()
{
    int n = strlen(s + 1);
    memcpy(s + n + 1, s + 1, n);	//复制成为双倍串
    int i = 1, j = 2, k;		//i, j不能同位,至少错一位
    while(i <= n && j <= n)		
    {
        for(k = 0; k < n && s[i + k] == s[j + k]; k ++ );		//尝试向后匹配
        if(k == n)  break;			
        if(s[i + k] > s[j + k])     i += k + 1;
        else    j += k + 1;
        if(i == j)  i ++;
    }
    int res = min(i, j);	//i, j其中 <= n的为最小
    return res;
}
0%