KMP 算法

KMP算法小结

**转载: **
KMP算法浅显理解

**摘要: **

考察目标字符串ptr：
ababaca
这里我们要计算一个长度为m的转移函数next。

next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。

比如：abcjkdabc，那么这个数组的最长前缀和最长后缀相同必然是abc。
cbcbc，最长前缀和最长后缀相同是cbc。
abcbc，最长前缀和最长后缀相同是不存在的。

注意最长前缀：是说以第一个字符开始，但是不包含最后一个字符。 比如aaaa相同的最长前缀和最长后缀是aaa。
　　对于目标字符串ptr，ababaca，长度是7，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]分别计算的是
a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀的长度。由于a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀是“”，“”，“a”，“ab”，“aba”，“”，“a”,所以next数组的值是[-1,-1,0,1,2,-1,0]，这里-1表示不存在，0表示存在长度为1，2表示存在长度为3。这是为了和代码相对应。

　　好，到此为止，假设循环进行到 第 q 次，即已经计算了next[q]，我们是怎么计算next[q+1]呢？

　　比如我们已经知道ababab，q=4时，next[4]=2（k=2，表示该字符串的前5个字母组成的子串ababa存在相同的最长前缀和最长后缀的长度是3，所以k=2,next[4]=2。这个结果可以理解成我们自己观察算的，也可以理解成程序自己算的，这不是重点，重点是程序根据目前的结果怎么算next[5]的）.，那么对于字符串ababab，我们计算next[5]的时候，此时q=5, k=2（上一步循环结束后的结果）。那么我们需要比较的是str[k+1]和str[q]是否相等，其实就是str[1]和str[5]是否相等！，为啥从k+1比较呢，因为上一次循环中，我们已经保证了str[k]和str[q]（注意这个q是上次循环的q）是相等的（这句话自己想想，很容易理解），所以到本次循环，我们直接比较str[k+1]和str[q]是否相等（这个q是本次循环的q）。
如果相等，那么跳出while()，进入if()，k=k+1，接着next[q]=k。即对于ababab，我们会得出next[5]=3。 这是程序自己算的，和我们观察的是一样的。
　　
　　如果不等，我们可以用”ababac“描述这种情况。 不等，进入while()里面，进行k=next[k]，这句话是说，在str[k + 1] != str[q]的情况下，我们往前找一个k，使str[k + 1]==str[q]，是往前一个一个找呢，还是有更快的找法呢？ （一个一个找必然可以，即你把 k = next[k] 换成k- -也是完全能运行的（更正：这句话不对啊，把k=next[k]换成k–是不行的，评论25楼举了个反例）。但是程序给出了一种更快的找法，那就是 k = next[k]。 程序的意思是说，一旦str[k + 1] != str[q]，即在后缀里面找不到时，我是可以直接跳过中间一段，跑到前缀里面找，next[k]就是相同的最长前缀和最长后缀的长度。所以，k=next[k]就变成，k=next[2]，即k=0。此时再比较str[0+1]和str[5]是否相等，不等，则k=next[0]=-1。跳出循环。
（这个解释能懂不？）

获取NEXT数组:

void cal_next(char *str, int *next, int len)
{
    next[0] = -1;//next[0]初始化为-1，-1表示不存在相同的最大前缀和最大后缀
    int k = -1;//k初始化为-1
    for (int q = 1; q <= len-1; q++)
    {
        while (k > -1 && str[k + 1] != str[q])//如果下一个不同，那么k就变成next[k]，注意next[k]是小于k的，无论k取任何值。
        {
            k = next[k];//往前回溯
        }
        if (str[k + 1] == str[q])//如果相同，k++
        {
            k = k + 1;
        }
        next[q] = k;//这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给next[q]
    }
}

JAVA FOR KMP

import java.util.ArrayList;
import java.util.List;

public class KMP {

    public static void main(String[] args){
        String str = "absbshdiffhsjhdgsabbaddabcbabdssedue";
        String parse = "abcbab";
        List<Integer> next = getNext(parse);


        int strlen = str.length();
        int parseLen = parse.length();

        int k=-1;//字符串匹配的位置，大于-1表示存在匹配的字符串

        int i=0;

        for (i=0;i<strlen;i++){
            while (k>-1 && parse.charAt(k+1) != str.charAt(i)){//如果有匹配的字符串，则从匹配的字符串里面先去查询一遍是否存在匹配，如果没有则
                k=next.get(k);
            }

            if (parse.charAt(k+1) == str.charAt(i)){//如果匹配，则让K表示匹配的位置
                k= k+1;
            }

            if (k==parseLen-1){//如果长度为匹配字符串的长度，则表示已匹配完成，退出
                break;
            }

        }

         System.out.println(str.charAt(i));
         System.out.println(i);

    }



    public static List<Integer> getNext(String parse){
        List<Integer> next = new ArrayList<Integer>();
        int strLen = parse.length();
        int k = -1;//k为循环到该字符串的最长前缀的位置
        next.add(0,k);//第一个默认为-1，只有一个字符串，所以没有最长前缀一说

        for (int i=1;i<strLen;i++){ //循环遍历每一个字符串 a,ab,abc,abca,abcba
            while (k>-1 && parse.charAt(k+1)!=parse.charAt(i)){//如果没有匹配成功，则k就必须回溯，如果回溯到最近一次的k=-1的位置，则跳出
                k = next.get(i);
            }

            if (parse.charAt(k+1) == parse.charAt(i)){//如果K+1（即上一步找到的最长前缀的位置+1）和上一步字符串+1的字符串匹配成功
                k = k+1;
            }

            next.add(i,k);
        }


        return next;
    }
}