KMP算法

Background

KMP算法是常会考察的算法，这次全部搞通。首先，这是一个典型的字符串匹配问题，起源是看九章算法基础班视频的时候，第一个就讲的strStr，首先来个直接给面试官的回答。

public int strStr(String source, String target){
        if (source == null || target == null) {
            return -1;
        }
        int i,j;
        for (i = 0; i < source.length() - target.length() + 1; i++) {
            for (j = 0; j < target.length(); j++) {
                if (source.charAt(i + j) != target.charAt(j)) {
                    break;
                }
            }
            if (j == target.length()) {
                return i;
            }
        }
        return -1;
    }

这个回答很直观，复杂度较高，但是清晰易懂。

Optimization

在strStr里，如果匹配不上的话，要把target往后移动一位，这个时候，其实是浪费了运算次数，可以优化跳转次数。

Analyse

首先，要明确的一点是，我们为什么要用KMP算法，这里就是因为如果是暴力的方法，即使i往后走了很多，如果在这个时候i和j对应的字符不匹配，那么i就会回到上次开始的后一位，我们要做的就是让i不回退，让j做相应的移动即可，这样可以在一定程度上优化匹配的过程，注意这里让i不回退是核心思想。
那么在匹配的时候，j应该怎么跳转呢，这个时候就引入了next数组，这个数组是为了