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

关于BF算法和KMP算法的具体解释，文章中有推荐博客的具体地址，可以在这些博客中找到详细的解释。

以下只有具体的java代码实现：

BF算法

package com.algorithm;/** * 字符串模式匹配的 Brute-Force算法（暴力法） * @author Administrator * */public class StrMatchBF {
       public static void main(String[] args) {        StrMatchBF strMatchBF = new StrMatchBF();        String iniStr = "hello world";        String patternStr = "world";        System.out.println(strMatchBF.indexOfStr(iniStr, patternStr)); // 输出6    }    /**     * 匹配字符串     * @param iniStr    原始字符串     * @param patternStr    模式字符串     * @return  如果模式字符串在原始字符串中存在，返回模式字符串在原始字符串中第一次出现的索引。     */    public int indexOfStr(String iniStr, String patternStr) {        if(iniStr == null || iniStr.length() <= 0 ||                 patternStr == null || patternStr.length() <=0)            return -1;        int iniLength = iniStr.length();        int patternLength = patternStr.length();        int i = 0, j = 0;        while(i < iniLength && j < patternLength) {            if(iniStr.charAt(i) == patternStr.charAt(j)) {                i++;                j++;            } else {                // 失配，回退                i = i - j + 1;                j = 0;            }        }        if(j == patternLength)            return i - patternLength;        else            return -1;    }}

KMP算法

package com.algorithm;/** * 字符串匹配的KMP算法 * @author Administrator * */public class StrMatchKMP {
       public static void main(String[] args) {        StrMatchKMP strMatchKMP = new StrMatchKMP();        String iniStr = "hello world";        String patternStr = "world";        System.out.println(strMatchKMP.indexOfStrKMP(iniStr, patternStr));    }    public int indexOfStrKMP(String iniStr, String patternStr) {        if(iniStr == null || iniStr.length() <= 0 ||                patternStr == null || patternStr.length() <= 0)            return -1;        // 得到模式串的next数组        int[] nextArr = getNextArray(patternStr);        int iniLength = iniStr.length();        int patternLength = patternStr.length();        int i = 0;  // 原始串索引        int j = 0;  // 模式串索引        while(i < iniLength && j < patternLength) {            if(j == -1 || iniStr.charAt(i) == patternStr.charAt(j)) {                i++;                j++;            } else {                j = nextArr[j];            }        }        if(j == patternLength)            return i - patternLength;        else             return -1;    }    /**     * 获取模式字符串的next数组     * @param str     * @return     */    public int[] getNextArray(String str) {        if(str == null || str.length() <= 0)            return null;        int length = str.length();        int[] nextArr = new int[length];        int j = 0;        int k = -1;        nextArr[0] = -1;        while(j < length - 1) {            if(k == -1 || str.charAt(j) == str.charAt(k)) {                j++;    // 匹配，移动                k++;                if(str.charAt(j) != str.charAt(k))                    nextArr[j] = k;                else                     nextArr[j] = nextArr[k];            } else {                k = nextArr[k];            }        }        return nextArr;    }}

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