本文共 1114 字，大约阅读时间需要 3 分钟。

/** * */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++; } else j = (next[j] - 1); } if (j > desStr.length() - 2) { return (i - desStr.length() + 1); } else return -1; }}

转载地址：http://cvini.baihongyu.com/