java实现的KMP算法

/** * */package com.baseframework;/** * @author sunyanan KMP算法 * */public class KMPAlgorithm {/** * 计算模式串的next函数 * * @param desStr * 模式串 * @return 模式串的next函数，用数组来保存 */private static int[] kmpNext(String desStr) {int len = desStr.length();int i = 0;int j = -1;int next[] = new int[len];while (i < len - 1) {if (j == -1 || (desStr.charAt(i) == (desStr.charAt(j)))) {i++;j++;if (desStr.charAt(i) != (desStr.charAt(j))) {next[i] = (j + 1);} else {next[i] = next[j];}} else {j = (next[j] - 1);}}return next;}/** * kmp的核心算法 * * @param sourceStr * @param desStr * @param pos * 从主串的第几个字符开始匹配 * @return 成功的话返回位置，失败的话返回-1，索引从0开始的 */public static int index(String sourceStr, String desStr, int pos) {int next[] = kmpNext(desStr);int i = 0;int j = 0;while (i < sourceStr.length() - 1 && j < desStr.length() - 1) {if (j == 0 || (sourceStr.charAt(i) == desStr.charAt(j))) {i++;j++;} elsej = (next[j] - 1);}if (j > desStr.length() - 2) {return (i - desStr.length() + 1);} elsereturn -1;}}