KMP 算法
1. 暴力匹配算法
在分析KMP算法前, 先看看暴力匹配算法是如何工作的.
暴力匹配算法的基本思想是: 从主串的第pos个字符起和模式串的第一个字符比较, 若相等,则继续逐个比较后续字符;否则从主串的下一个字符起再重新和模式串的字符比较. 依次类推, 直至模式串T中的每个字符和主串S中的一个连续的字符序列相等, 则匹配成功, 否则匹配不成功.
例如
主串S: S1 S2 S3 S4 ...... Sn; 模式串T: T1 T2 T3 T4 ...... Tn
当S[i] == T[j]时, 则i++, j++
当S[i] != T[j]时, 则i指针回溯到S2处, j指针回到起始位置T1处再进行匹配
假设主串S中有m个字符, 模式串T中有n个字符, 那么暴力匹配算法的时间复杂度可以表示为O(m*n)
小思考
-
当主串中S[i] != T[j]时, 主串的i指针是否需要回溯到本次匹配的第一个字符的下一个位置呢?
Back.png
由上图我们可以看出, i指针回溯的目的是为了让模式串T分别从主串S的S2,S3字符处开始匹配, 避免漏掉模式串T从主串的S2字符处或者S3字符处与主串S产生匹配的情况; 但是我们已知S1S2S3 == T1T2T3, 即 S1 == T1, S2 == T2, S3 == T3, 所以我们只需要拿T1与T2,T3进行比较, 即可判断模式串T是否会在S2或S3处开始于主串匹配, 据此我们可以通过只移动模式串的指针j而不移动主串的i指针来继续进行模式匹配的目的.
结论: 在整个模式匹配的过程中, 主串i指针可以不回溯
KMP 算法
KMP 算法相对于暴力匹配算法的改进在于: 在模式匹配的过程中, 如果出现了失配的情况, 不需要回溯主串的i指针, 而是利用已经得到的"部分匹配"的结果将模式串T向右"滑动"尽可能远的距离,再继续与主串进行比较
-
下面以主串S, 模式串T为例, 分析当S与T失配时, 模式串T的j指针应该如何移动?
Screen Shot 2018-05-19 at 3.16.07 PM.png
此时S[i] != T[j]
那么假设此时模式串T的指针j需要回溯到k位置再与主串S进行比较, 如图
这里的k需要满足的条件是: T[0]T[1]...T[k-1] == T[j-k+1]...T[j-1]
从这里我们可以看出, 模式串T中k位置位主串S是无关的, 它是通过模式串本身的特性确定的; 由此我们在进行模式匹配前, 可以先对模式串T的各个位计算其k值; 当模式串T与主串S失配时, 我们就可以直接根据模式串T的失配位获取对应的k值, 然后让模式串T的j指针回溯到k位置再与主串S进行比较
- 如何确定模式串T各个位的k值?
这里我们先确定k值的含义
k指的是当模式串中指针j所指向的字符与主串中指针i所指向的字符失配时, 在模式串T需要重新和主串S中i指针指向的字符进行比较的字符的位置
设next(j) = k, 则模式串存在下列关系:
T[0]T[1]...T[k-1] == T[j-k+1]...T[j-1]
其中k为满足1<k<j的某个值, 此时next(j + 1) = ?可能有两种情况:
(1) T[k] = T[j]
表明在模式串中T[0]T[1]...T[k] == T[j-k+1]...T[j], 则next(j + 1) = next(j) + 1
(2) T[k] != T[j]
表明在模式串中T[0]T[1]...T[k] != T[j-k+1]...T[j], 此时可以把求next的函数值的问题看成是一个模式匹配的问题, 整个模式串既是主串也是模式串, 而当前的匹配过程中, 已有T[0]T[1]...T[k] == T[j-k+1]...T[j], T[k] != T[j], 现将模式右滑至以模式中的第next(k)个字符和主串中的第j个字符比较, 如果next(k) = k', 且T[j] = T[k'], 则说明在主串中第j+1个字符前存在一个长度为k'的最长子串和模式串中从首字符起长度为k'的子串相等,即T[0]T[1]...T[k'] == T[j-k'+1]...T[j], 此时next(j + 1) = next(k) + 1; 同理如果T[j] != T[k'], 则继续进行上述过程直至T[j]和模式中某个字符匹配成功或者不存在任何k'满足条件,则next(j + 1) = 1.
总结
- 当j = 1时, next(j) = 0; 此时主串i指针右移一位, 即i++; 模式串从主串的第i位开始匹配
- 当j = 0时, next(j) = 1; 此时模式串j指针回溯到第一位再与主串第i位进行匹配
- 当j = Max{k|1 < k < j, 且T[0]T[1]...T[k-1] == T[j-k+1]...T[j-1]}时, 模式串指针j回溯到next(j)处再与主串第i位进行匹配
KMP算法实现
//
// main.c
// KMP
//
// Created by 肖仲文 on 2018/6/3.
// Copyright © 2018 肖仲文. All rights reserved.
//
#include <stdio.h>
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN + 1]; // 0号单元存放串的长度
/**
生成一个值为chars的串
@param T 串
@param chars 字符串常量
*/
void strAssign(SString T, const char *chars) {
if (chars == NULL) {
return;
}
int index = 0;
while (*(chars + index) != '\0') {
T[index + 1] = *(chars + index);
index++;
}
T[0] = index;
}
/**
求模式串T的next函数值并保存到数组next
@param T 模式串
@param next next值数组
*/
void get_next(SString T, int next[]) {
int i = 1;
int j = 0;
next[i] = j;
while (i < T[0]) {
if (j == 0 || T[i] == T[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
/**
KMP算法
@param S 主串
@param T 模式串
@param next 模式串的next值数组
@return 模式串与主串匹配时的位置, 不匹配返回0
*/
int index_kmp (SString S, SString T, int next[]) {
int i = 1;
int j = 1;
while (i <= S[0] && j <= T[0]) {
if (j == 0 || S[i] == T[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j > T[0]) {
return i - T[0];
} else {
return 0;
}
}
int main(int argc, const char * argv[]) {
// 定义主串和模式串
SString mainStr, patternStr;
// 初始化主串和模式串
strAssign(mainStr, "ababcabcacbab");
strAssign(patternStr, "abcac");
// next值
int next[patternStr[0] + 1];
get_next(patternStr, next);
// kmp
int pos = index_kmp(mainStr, patternStr, next);
printf("pos = %d\n", pos);
return 0;
}
