模式匹配算法----KMP算法以及next数组的解法

KMP算法：

求字符串匹配（也叫模式匹配）的算法，即给定一个字符串，求其某一子串在其中出现的位置。

例如：给定字符串为abcabaaabaabcac，求其子串abaabcac在其中出现的位置。

结果为7

对于这种问题，没有经验的编程者通常会采用逐个匹配的方法，来得出结果。这就是最简单一种算法思想。

1. 逐个进行比较，如果相同，就继续比较下一个，但是我们可以看到下图中，c与a不相同，这就是所谓的“失配”。
2. 当发生失配，我们会将子字符串逐个后移，直到新的匹配建立，再逐个比较

根据上面的方法，我们可以看到第二步有两个图，这是为什么呢？这是因为当出现失配时候，字符串每次后移一个的方法，不能够立刻建立匹配，还需要继续后移才能建立。也就是说，这种情况下，后移两个才能建立匹配。

当然这个例子比较小，只出现了两次这种情况，但是如果是较大的数据，这种冗余操作是十分低效的。这也就是KMP算法优化的地方。

KMP算法会创建一个next[]数组，用来保存一个字符失配后，到底跳转到第几个的位置才能更快速的建立匹配。这里用了跳转这个词，因为并不是向后移动next[i]位，而应该是往后移动，是失配位与第next[i]位相对。这个数组是KMP算法的核心。下表为子字符串abaabcac的next数组，（至于为什么叫next，因为当初创造算法的三个人就是这么叫的，对，就是三个人创的这个算法，这三个人的名字首字母就是K，M，P）

next数组求解思路：

以abaabcac为例

第一位和第二位分别为0和1，这是一定的。之后的每一位的next[i]，需要看第[i-1]位的值与第[第i-1位的next值]位的值相比，这里比较难理解，不明白的读者可以参考下面的例子，实际上如果我们如果求next[i]，需要看的是i-1是否等于next[i-1] ，如果不同，查看第i-1位的next值是否为1，如果为1，则需继续比较，如果为0，则可以得出结果。而相同的结果为next[i-1]+1，

第一位：next[1]=0

第二位：next[2]=1

第三位：将第二位的值"b"与第[第二位的next值=1]位的值"a"相比，不同，为1（因为第一位的next值为0，所以不需要继续比较）

第四位：将第三位的值"a"与第[第三位的next值=1]位的值"a"相比，相同，则为next[3]+1=2

第五位：将第四位的值"a"与第[第四位的next值=2]位的值"b"相比，不同，因为第二位的next值为1，再将第四位的值"a"与第[第二位的next值=1]位的值"a"相比，相同，则为next[2]+1=2

第六位：将第五位的值"b"与第[第五位的next值=2]位的值"b"相比，相同，则为next[5]+1=3

第七位：将第六位的值"c"与第[第六位的next值=3]位的值"a"相比，不同，因为第三位的next值为1，再将第六位的值"c"与第[第二位的next值=1]位的值"a"相比，不同，则为1

第八位：将第七位的值"a"与第[第七位的next值=1]位的值"a"相比，相同，则为next[7]+1=2

求解next数组代码：我们从第3位开始，

private static int[] get_Next(String str){ 
    int[] next = new int[str.length()+1];  
    int j = next[2];
    // 这里next[1]和next[2]直接赋值
    next[1] = 0;
    next[2] = 1;
    // 第2位之后的next,为什么从2开始，不是已经赋值了吗？这在于str.charAt(0)为字符串的第一个字母
    for(int i = 2; i < str.length(); i++) {  
        while(j > 0 && str.charAt(i-1) != str.charAt(j)) {
        	j = next[j]; 
        }
        if(str.charAt(i-1) == str.charAt(j)) {
        	j++;
        }
        next[i] = j;
    }  
    return next; 
}

根据next数组，我们再来做一遍这个题目：给定字符串为abcabaaabaabcac，求其子串abaabcac在其中出现的位置。

1.创建匹配，第4个字符发生失配

2.使失配位与第next[4]=2位相对，但是这是第二个字符又失配了

3.使失配位与第next[2]=1位相对，此时第一个字符就失配

4.使失配位与第next[1]=0位相对，注意我们的next数组是从1开始算的，所以相当于整体后移一个单位，下图的失配位实际是"c"

虽然上面这个流程看不太出来KMP算法的优势，但还是比暴力的方式要好很多的。当然还有一种BM算法效率比KMP算法还好。有兴趣的读者可以参考深入浅出讲算法思想--时空权衡算法思想分析及应用

完整代码如下：

public class Main {
public static void main(String[] args) {
String str = "abaabcac";
String orig ="aabaabcac";
int[] next = get_Next(str);
for (int i = 1; i < next.length; i++) { System.out.print(next[i] + " "); } System.out.println(); search(orig, str, next);
}

//next[i]表示的是str的"部分匹配表",这个表表示的是str前缀与后缀的最长公共字符串的长度
private static int[] get_Next(String str){ 
    int[] next = new int[str.length()+1];  
    int j = next[2];
    // 这里next[1]和next[2]直接赋值
    next[1] = 0;
    next[2] = 1;
    // 第2位之后的next,为什么从2开始，不是已经赋值了吗？这在于str.charAt(0)为字符串的第一个字母
    for(int i = 2; i < str.length(); i++) {  
        while(j > 0 && str.charAt(i-1) != str.charAt(j)) {
        	j = next[j]; 
        }
        if(str.charAt(i-1) == str.charAt(j)) {
        	j++;
        }
        next[i] = j;
    }  
    return next; 
}  

//orig为主串，而find为模式串，查找匹配位置以及匹配长度  
private static void search(String orig, String find, int[]next){  
    int j = next[0];  
    for(int i = 0;i < orig.length(); i++){  
        while(j > 0 && orig.charAt(i) != find.charAt(j))  
            j = next[j];  
        if(orig.charAt(i) == find.charAt(j)){  
            j++;  
        }
        if(j == find.length()){  
            System.out.println("find at position " + (i - j+1));    
            System.out.println(orig.subSequence(i - j + 1, i + 1));    
            j = next[j];
        }
    }
}

}

上面代码是完全正确的，但是细心的读者如果将next打印出来后，会发现next实际上为下面的nextval这种情况

i 1 2 3 4 5 6 7 8 str.charAt(i) a b a a b c a c next[i] 0 1 1 2 2 3 1 2 nextval[i] 0 0 1 1 2 0 1 0 网上的代码各种各样，无论是next数组还是nextval数组都是各种写法，是在找不到合适的代码贴上，过一阵子再说吧，有兴趣的读者可以参考KMP算法及next数组详解