KMP算法，无解释，仅代码

KMP算法（摘自百度百科）：KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特-莫里斯-普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度为O(m+n)。

JAVA实现版本一（自己手写，很乱，建议看下一个版本）

public class KMP {
    static int[] getNext(String t) {
        int next[]=new int[t.length()];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int j = 0;
        while (i < t.length()) {
            if (t.charAt(i - 1) == t.charAt(j)) {
                j++;
                next[i] = j;
                i++;
            } else {
                j = next[j];
                if (j == -1) {
                    j++;
                    next[i] = j;
                    i++;
                }
            }
        }
        return next;
    }

    static int KMPSearch(String target,String text){
        int[] next = getNext(target);
        int i=0;
        int j=0;
        while(j<text.length()){
            if (target.charAt(i)==text.charAt(j)){
                if (i==target.length()-1){
                    return j-i;
                }else{
                    i++;
                    j++;
                }
            }else{
                i=next[i];
                if (i==-1){
                    i++;
                    j++;
                }
            }
        }
        return -1;
    }
}

JAVA实现版本二（取自CSDN博客上的，稍作改动，个人觉得代码非常简洁）

public class KMP {
    static int[] getNext(String s){
        int next[]=new int[s.length()];
        next[0]=-1;
        int i=0;
        int j=-1;
        while(i<s.length()-1){
            if (j==-1||s.charAt(i)==s.charAt(j)){
                i++;
                j++;
                next[i]=j;
            }else{
                j=next[j];
            }
        }
        return next;
    }
    static int KMPSearch(String target,String text){
        int i=0;
        int j=0;
        int[] next = getNext(target);
        while(j<text.length()){
            if (i==target.length()-1&&target.charAt(i)==text.charAt(j)){
                return j-i;
            }
            if(j==-1 || target.charAt(i)==text.charAt(j)){
                i++;
                j++;
            }else{
                i=next[i];
            }
        }
        return (-1);
    }
}

GoLang实现：

func getNext(s string) []int {
    next:=make([]int,len(s))
    next[0]=-1
    i,j:=0,-1
    for ; i< len(s)-1;  {
        if j==-1||s[i]==s[j] {
            i++
            j++
            next[i]=j
        }else {
            j=next[j]
        }
    }
    return next
}
func KMPSearch(target string,text string) int {
    i,j:=0,0
    next := getNext(target)
    for ; j< len(text);  {
        if i==len(target)-1&&target[i]==text[j] {
            return j-i
        }
        if j==-1||target[i]==text[j] {
            i++
            j++
        }else {
            i=next[i]
        }
    }
    return -1
}

Python实现：

def get_next(s):
    nex = [-1]
    i, j = 0, -1
    while i < len(s)-1:
        if j == -1 or s[i] == s[j]:
            i = i+1
            j = j+1
            nex.append(j)
        else:
            j = nex[j]
    return nex


def kmp_search(tar, text):
    i, j = 0, 0
    ne = get_next(tar)
    while j < len(text):
        if i == len(tar)-1 and tar[i] == text[j]:
            return j-i
        if j == -1 or tar[i] == text[j]:
            i = i+1
            j = j+1
        else:
            i = ne[i]
    return -1