KMP 算法详解

package org.javaadu.string;
import java.util.List;
public class StringSearchDemo {
    public static void main(String[] args) {        String text = "aabaabaaf";        String pattern = "aabaaf";
        boolean kmpRes = kmpSearch(text, pattern);        System.out.println("kmpRes:" + kmpRes);    }
    /**     * 利用KMP算法求解pattern是否在text中出现过     *     * @param text    文本串     * @param pattern 模式串     * @return pattern在text中出现，则返回true，否则返回false     */    public static boolean kmpSearch(String text, String pattern) {        //部分匹配数组，就是很多算法实现中的next数组        int[] partMatchTable = buildPartMatchTable(pattern);        //text中的指针        int i = 0;        //pattern中的指针        int j = 0;
        while (i < text.length()) {            if (text.charAt(i) == pattern.charAt(j)) {                //字符匹配，则两个指针同时后移                i++;                j++;            } else if (j > 0) {                //字符失配，则利用next数组，异动j指针，避免i指针回退                j = partMatchTable[j - 1];            } else {                //pattern中的第一个字符就失配了                i++;            }
            if (j == pattern.length()) {                //搜索成功                return true;            }        }        return false;    }
    private static int[] buildPartMatchTable(String pattern) {        //初始化        int[] partMatchTable = new int[pattern.length()];        int prefixLen = 0;        next[0] = 0;        int i = 1;
        while (i < pattern.length()) {            //pattern[prefixLen]，表示目前最长相等子串的最后一位            //pattern[i]，表示目前正在处理的子串的最后一位的字符            if (pattern.charAt(prefixLen) == pattern.charAt(i)) {                //如果它俩相等，说明找到了更长的相等子串                prefixLen++;
                partMatchTable[i] = prefixLen;                i++;//处理下一个i的字符            } else {                //如果不相等，则需要尝试下更短1位的子串是否满足要求，因此这里要把再次循环尝试下：仅仅改变prefixLen的值，不改变i的值                prefixLen = next[prefixLen - 1];                if (prefixLen == 0) {                    //如果实在没有合适的，则说明当前正在处理的子串的最长相等前后缀的长度是0                    partMatchTable[i] = 0;                    i++;//处理下一个i的字符                }            }        }        return partMatchTable;    }}