KMP（构建next数组）

字符串匹配算法KMP, 核心思想是尽可能利用已经匹配的结果, 跳过尽可能多的不需要匹配的情况

重点和难点都在next数组的建立上

1. KMP算法的next数组求解

以模式串 a b a c a b 为例

a b a c a b

// 初始, 两个指针都在下标0的位置, 从此开始, current指针不断后移,

// 并和头指针比较, 不同填0，相同则为前一个值加1

 | |

 v v

 a b a c a b

 0 0

 |   |

 v   v

 a b a c a b

 0 0 1

 |     |

 v     v

 a b a c a b

 0 0 1 0

 |       |

 v       v

 a b a c a b

 0 0 1 0 1

 |         |

 v         v

 a b a c a b

 0 0 1 0 1 2

　　其中, 当在模式字符串i位置匹配失败的时候, i 跳转到next[i-1]的值

如上所示, 则当第二个字符a匹配失败的时候, 返回第一个字符b位置对应的next值, 为0.看上去没问题

但是, 当最后一个字符b匹配失败的时候, 根据该算法应返回1.意味着, 我们希望可以像下面这样继续:

abaca?

abacab 进行继续匹配。事实上这是有问题的。根据之前的匹配结果, 已知? <> 'b' ,这次匹配注定是失败的，是没有意义的，应返回0

2. 自己尝试改写的求next方法

我们希望得到这样的结果:

abacab

000100

并在模式串i位置匹配失败时, 返回next[i]的值

根据kmp指导思想, 希望可以利用已经匹配的结果, 也就是重叠已经匹配的结果和模式串中的前缀部分.

这需要模式串中有跟模式串前缀相同的字符串存在, 但是为了避免匹配失败时，再度尝试与已知匹配结果的字符进行匹配，先分析如下:

例: abacab

首先满足第一个条件, 就是模式串中存在模式串前缀的内容，首要保证的是, 模式串的第一个字符在模式串中存在多个

例子中有两处

    1   2
    |   |
a b a c a b

接下来, 两处中能匹配模式串前缀的最长字符串分别为:

1 : a 2 : ab

第二个条件, 减少已知结果的匹配

1. 当1处的a匹配成功时,但c匹配失败时, 因为模式串前缀ab与ac有重叠但不完全相同

可以重叠匹配像这样:

aba?

abacab ?虽然与'c'匹配失败, 但不一定与'b'匹配失败，这样的匹配是有必要的

2. 当2处的a匹配成功, 但b匹配失败时, 因为模式串前缀ab与ab完全相同,所以不可以进行重叠匹配,原因:

abaca? abaca?

abacab 此时已知?与'b'不匹配, 这样的匹配是没有必要的应该这样: abacab 即直接跳回最开始的位置重新匹配

注意到两者的差别, 1.处时, 虽然在非模式串前缀匹配失败, 可进行重叠匹配, 2处时在模式串前缀匹配失败, 不可重叠匹配

（模式串并不一定指1之前的,如abcacabcab 这里模式串前缀也可以是abcac, 而不一定是abc）

于是有下面的推导:

最开始next数组全部用0初始化
两个指针在0下表
state 表示是否在前缀状态

state = 0
| |
v v
a b a c a b
0 0 0 0 0 0

state = 1// 此时开启前缀模式
|   |
v   v
a b a c a b
0 0 0 0 0 0

state = 0//state为1时, 头指针跟着向前走, 当state从1变为0时, next记录此时头指针的位置,头指针回到初始状态
  |   |
  v   v
a b a c a b
0 0 0 1 0 0

state = 1
|       |
v       v
a b a c a b
0 0 0 1 0 0

state = 1
  |       |
  v       v
a b a c a b
0 0 0 1 0 0

代码实现:

int* getNext(const char *target) {
    int *next;
    int head, current, len, state;
    len = strlen(target);
        // 生产next数组
    next = (int *)malloc(sizeof(int) * len);
        // 出事化工作
    head = 0;
    current = 1;
    next[0] = 0;
    memset(next, 0, len * sizeof(int));
    state = 0; // 非前缀状态
    // 遍历target产生next数组
    // 原理, 尽可能利用已经匹配的结果进行错位
    while(current < len) {
        if(target[head] == target[current]) {
                        // 如果相等, 进入前缀状态, head 指针跟着current指针后移
            state = 1;
            head++;
            current++;
        }else {
            if(state == 1) {
                                // state 从0变为1, 设置next值
                next[current] = head;
                                 // 回到初始状态
                     head = 0;
                     state = 0;
            }
            else {
                current++;
            }
        }
    }
    return next;
}

算法实现:

/*
    这部分代码的实现可能有点乱, 不太优美, 回头再改改~~
*/
int KMP(const char *source, const char *target) {
    int *next;
    // 获得next数组
    next = getNext(target);
    int source_index = 0;
    int source_len = strlen(source);
    int target_index = 0;
    int target_len = strlen(target);
    while(source_index < source_len && target_index < target_len) {
        if(source[source_index] == target[target_index]) {
            source_index++;
            target_index++;
        }else {
            // 跳过
            if(target_index == 0)
                source_index++;
            else {
                printf("Skip %d to %d for %c where %d\n", target_index, next[target_index - 1], source[source_index], source_index);
                target_index = next[target_index];
            }
        }
    }
    if(source_index == source_len)
        return -1;
    return source_index - target_len;
}

算法实现时的问题:

1. 为处理字符串为空字符串的情况

2. 为考虑传入NULL值的情况

在KMP函数最前面加入一下代码后，可以过lintcode的strStr题目

if(source == NULL || target == NULL)

    return -1;

if(source == "" && target == "")

    return 0;

KMP（构建next数组）

推荐阅读