字符串模式匹配中BF算法和KMP算法的java实现

关于BF算法和KMP算法的具体解释，文章【博客地址】：KMP字符串匹配算法与next数组中有推荐博客的具体地址，可以在这些博客中找到详细的解释。

以下只有具体的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;
    }
}