简单的模式匹配算法

这种算法的关键在于，指针i会进行回退，而模式串不去移动。这里的算法关键之处在于理解指针i和j的处理关系。算法时间复杂度为：

简单的模式匹配算法时间复杂度 ，并且m为主串，n为模式串。

# use type hint to get a smart hint
def index(target: str, pattern: str) -> int:
    # 这一波使用普通的算法，即i回退
    i = 0
    j = 0
    len_i = len(target)
    len_j = len(pattern)
    while (i<= len_i-1) and (j<=len_j-1):
        if target[i] == pattern[j]:
            i += 1
            j += 1
        else:
            # 回退
            i = i - j + 1
            print ("i value: %d"%i)
            j = 0
        print("j is %d"%j)
    if (j > len_j-1):
        return i - len_j
    else:
        return -1

print(index("abc", "abc"))
print(index("aabc", "abc"))

算法关键点解释

而上述也是写简单的模式匹配算法中应该注意的关键，这是算法出不出错的最关键的保证。

改进的模式匹配算法——KMP算法

KMP算法全称为克努特—莫里斯—普拉特操作，此算法时间复杂度为：

KMP算法时间复杂度 ,其与之前算法最大的不同在于：指针i不回退，而是移动模式串。因此，算法的关键部分在于，在匹配不成功的时候，我们该如何移动模式串呢，又该移动多少位的模式串呢？
因此，这里就涉及到next[]数组的计算了，而计算next[]数组的时候我们必须要明白为何要这样子去计算。我们称计算next[]的函数为失效函数。
失效函数
Python代码如下：

def get_next(pattern:str) ->list:
    # 求失效函数值序列
    length = len(pattern)
    next = [None]*length
    next[0] = -1  # 失效序列初始值设置为-1（某些国内教材设定为0）
    i = 0
    j = -1  # represents the value of next[]
    while (i < length-1):
        # mmp C/C++写多了，括号习惯了
        if (j == -1 or pattern[i] == pattern[j]):
            # j == -1 means this is the first value, need process specially
            i += 1
            j += 1
            next[i] = j
        else:
            j = next[j]
    return next

上述代码里，最关键也是最难理解的部分就是while循环里面的内容。而while循环实际上是通过前面计算的数据去求得后面next数组的值。

前缀方式理解代码
另外，还有一种改进的方式：

def get_nextval(pattern:str) ->list:
    # 改进的失效函数序列值算法
    length = len(pattern)
    next = [None]*length
    next[0] = -1  # 失效序列初始值设置为-1（某些国内教材设定为0）
    i = 0
    j = -1  # represents the value of next[]
    while (i < length-1):
        if (j == -1 or pattern[i] == pattern[j]):
            # j == -1 means this is the first value, need process specially
            i += 1
            j += 1
            if pattern[i] == pattern[j]:
                next[i] = next[j]
            else:
                next[i] = j
        else:
            j = next[j]
    return next

这里的关键部分在于：

if pattern[i] == pattern[j]:
                next[i] = next[j]
            else:
                next[i] = j

这里的意思是，既然我target[i]和pattern[i]进行了对比，然后发现本身就已经不同了，那我就该回退至pattern[next[i]]的值，可是这个值如果和pattern[i]相同的话，那就没有对比的必要了，也就省去了一次多余的比较了。

KMP算法

def kmp(target:str, pattern:str) -> int:
    # kmp(非改进)算法，模式匹配
    next = get_next(pattern)  # 得到失效值序列
    i = 0
    j = 0
    len_i = len(target)
    len_j = len(pattern)
    while i<=len_i-1 and j <=len_j-1 :
        if target[i] == pattern[j] or j == -1:
            i += 1
            j += 1
        else:
            j = next[j]
            # if j == -1:
            #     i += 1
            #     j += 1
    
    if j >= len_j-1:
        return i-len_j
    else:
        return -1

这里可以注意下我们注释的部分，因为Python里面list[-1]表示取数组最后一项，而我们这里-1代表需要使i++，所以我们要处理好这部分的逻辑。

C语言实现过程

/*
written at 2018-5-28 19:27:42
KMP算法中计算next的实现方式
*/
#include <string.h>
#include <stdio.h>

void next1(char *s, int *next){
    // s为字符串，next为失效函数序列
    int length = strlen(s);  // 字符串的长度
    int i = 0; int j = -1;
    next[0] = -1;
    while (i < length-1){
        if (j==-1 || s[i] == s[j]){i++; j++;next[i] = j;}
        else{j = next[j];}
    }
}

void next_val(char *s, int *next){
    // 改进版本的失效函数
    int length = strlen(s);
    int i = 0; int j = -1;
    next[0] = -1;
    while (i<length -1){
        if (j==-1 || s[i] == s[j]){
            i++;
            j++;
            if (s[i] != s[j]) next[i] = j;
            else next[i] = next[j];
        }else{
            j = next[j];
        }
    }
}

int kmp(char *s, char *pat, int pos){
    // K(nuth)M(orris)P(ratt)算法
    int i = pos; int j = 0;
    int length_s = strlen(s);
    int length_pat = strlen(pat);
    // calculate the array of the next function
    int next[length_pat];
    next1(pat, next);
    while(i<length_s && j<length_pat){
        if (j == -1 || s[i] == pat[j]){i++; j++;}
        else j = next[j];
    }
    if(j>= length_pat) return i - length_pat;
    else return 0;  // pat fail
}

void main(){
    char *s = "peng jidong";
    char *pat = "jidong";
    int ans = kmp(s, pat, 1); 
    printf("ans is %d\n", ans);
    // printf the answer to examine it right or not
    for (int i=ans; i<strlen(s);++i){
        printf("%c",s[i]);
    }
}

/*
************output**********
ans is 5
jidong
*/