java实现字符串匹配

暴力匹配

/**
 * 暴力匹配
 *
 * @param str1 需要找的总字符串
 * @param str2 需要找到的字符串
 * @return 找到的字符串的下标
 */
private static int violence(String str1, String str2) {
    char[] s1 = str1.toCharArray();
    char[] s2 = str2.toCharArray();
    int s1Len = s1.length;
    int s2Len = s2.length;

    // 指针，分别指向两个字符串
    int i = 0;
    int j = 0;

    // 保证匹配时不越界
    while (i < s1Len && j < s2Len) {
        // 第一个字符匹配上了
        if (s1[i] == s2[j]) {
            ++i;
            ++j;
        } else {
            i -= (j - 1);
            j = 0;
        }
    }

    // 判断是否成功
    if (j == s2Len) {
        return i - j;
    } else {
        return -1;
    }
}

KMP算法

/**
 * KMP算法
 *
 * @param str1 源字符串
 * @param str2 子串
 * @param next 匹配值表
 * @return 对应下标，没有为-1
 */
private static int kmp(String str1, String str2, int[] next) {
    for (int i = 0, j = 0; i < str1.length(); ++i) {

        while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
            j = next[j - 1];
        }

        if (str1.charAt(i) == str2.charAt(j)) {
            j++;
        }

        if (j == str2.length()) {
            return i - j + 1;
        }
    }
    return -1;
}

/**
 * @return dest的部分匹配表
 */
private static int[] getkmpNext(String dest) {
    int length = dest.length();
    int[] next = new int[length];
    next[0] = 0;

    for (int i = 1, j = 0; i < length; i++) {

        while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
            j = next[j - 1];
        }

        if (dest.charAt(i) == dest.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    return next;
}