回到顶部暗色模式

String.indexOf方法和KMP算法简介

1. `String.indexOf`

子字符串查找是字符串的一种基本操作：给定一段长度为 $N$ 的文本和一个长度为 $M$ 的模式 ( $pattern$ ) 字符串，在文本中找到一个和该模式相符的子字符串。对于一般的暴力式方法，在最坏的情况下运行时间与 $MN$ 成正比，但是在处理许多应用程序中的字符串时 ( 除了一些极端情况外 )，它的实际运行时间一般与 $M + N$ 成正比。另外，它很好地利用了大多数计算机系统中标准的结构特性，因此即使是更加巧妙的算法也很难超越它经过优化后的版本的性能。

public static int search(String pat, String txt) {
    int M = pat.length();
    int N = txt.length();
    for (int i = 0; i <= N; i++) {
        int j;
        for (j = 0; j < M; j++)
            if (txt.charAt(i + j) != pat.charAt(j))
                break;
        if (j == M) return i;
    }
    return N;
}

$String.indexOf$ 提供了子字符串查找功能，实现方式也是类似于上面的暴力式方法：

/**
* String和StringBuffer共享的搜索方法，源串和模式串均由字符数组组成
*
* @param source 待搜索的串
* @param sourceOffset 源串偏移量
* @param sourceCount 源串长度
* @param target 模式串
* @param targetOffset 模式串偏移量
* @param targetCount 模式串长度
* @param fromIndex 起始搜索位置
*/
static int indexOf(char[] source, int sourceOffset, int sourceCount,
        chat[] target, int targetOffset, int targetCount,
        int fromIndex) {
    // 起始位置大于源串长度
    if (fromIndex >= sourceCount) {
        return (targetCount == 0 ? sourceCount : -1);
    }
    // 起始位置小于0，设为0
    if (fromIndex < 0) {
        fromIndex = 0;
    }
    // 模式串长度为零，返回起始位置
    if (targetCount == 0) {
        return fromIndex;
    }
    // 获取模式串第一个字符以及源字符串最大长度
    char first = target[targetOffset];
    int max = sourceOffset + (sourceCount - targetCount);
    // 从偏移量开始查找
    for (int i = sourceOffset + fromIndex; i <= max; i++) {
        // 首字符不匹配，查询下一个匹配位置
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }

        if (i <= max) {
            // 第二个字符位置
            int j = i + 1;
            // 剩余待匹配长度
            int end = j + targetCount - 1;
            // 匹配剩余串
            for (int k = targetOffset + 1; j < end && source[j]
                    == target[k]; j++, k++);
            // 匹配成功，返回起始索引
            if (j == end) {
                return i - sourceOffset;
            }
        }
    }
    // 匹配失败，返回-1
    return -1;
}

2. `KMP`

KMP算法的基本思想是当出现不匹配时，就能知晓一部分文本的内容 ( 因为在匹配失败之前它们已经和模式相匹配 )。我们可以利用这些信息避免将指针回退到所有这些已知的字符之前。例如对于字符串 $ABCDABD$ ，当我们匹配到倒数第一个字符即 $B$ 的时候，如果发现不匹配，我们没有必要再将模式指针移到开头，而是移到第三个字符即 $C$ ，因为我们已经知道了前面两个字符必定为 $AB$ 。
为了实现上述回退操作，我们需要实现一个 $next[\ ]$ 数组记录回退位置。我们可以将字符串分为前缀和后缀两个部分，每个字符都有对应的前缀和后缀，例如对于 $ABAB$ ，有：

索引	$0$	$1$	$2$	$3$
前缀		$A$	$AB$	$ABA$
后缀	$BAB$	$AB$	$B$

而构造的 $next[\ ]$ 数组记录的就是除当前字符外最长的相同前缀后缀。简单的来讲就是对于每个从 $0$ 开始的子串，寻找其前缀后缀集合中最长的公有元素。再以 $ABAB$ 为例：

$A$ 的前缀和后缀均为空集，没有公有元素；
$AB$ 的前缀为 ( $A$ )，后缀为 ( $B$ )，没有公有元素；
$ABA$ 的前缀为 ( $A$, $AB$ )，后缀为 ( $BA$, $A$ )，最长公有元素为 $A$ ，长度为 $1$ ；
$ABAB$ 的前缀为 ( $A$, $AB$, $ABA$ )，后缀为 ( $BAB$, $AB$, $B$ )，最长公有元素为 $AB$ ，长度为 $2$ 。

获取了最长公有元素长度后，就可以构造 $next[\ ]$ 数组了，构造的时候只需要将首位设为 $-1$ ，然后将求得的数字统一右移一格即可。

模式串	$A$	$B$	$A$	$B$
数组	$-1$	$0$	$0$	$1$

但是显然，对于每个 $index[i]$ ，如果每次都要计算前缀和后缀，然后比较统计长度，那么花费的时间可能会比暴力搜索要久。我们可以利用动态规划的思想，利用先前求得的值。例如对于 $ABCDABCE$ ，我们已经计算出前 $7$ 位值如下：

模式串	$A$	$B$	$C$	$D$	$A$	$B$	$C$
最长前后缀公有串长度	$0$	$0$	$0$	$0$	$1$	$2$	$3$
$next$	$-1$	$0$	$0$	$0$	$0$	$1$	$2$

此时对于第 $j = 8$ 位 $E$ ，可以发现有 $pattern[j - 1] == pattern[next[j - 1]]$ ，也就意味着第 $j - 1$ 个子串的前后缀最长公有元素的长度必定为第 $j - 2$ 个子串的长度加 $1$ ，也即 $index[j] = index[j - 1] + 1$ 。
而对于不相等的情况如 $ABCDABDE$ ，有：

模式串	$A$	$B$	$C$	$D$	$A$	$B$	$D$
最长前后缀公有串长度	$0$	$0$	$0$	$0$	$1$	$2$	$0$
$next$	$-1$	$0$	$0$	$0$	$0$	$1$	$2$

这时再对第 $j = 8$ 位 $E$ 比较，可以发现 $pattern[j - 1] != pattern[next[j - 1]]$ 。这时就需要递归索引，即令 $k = next[j - 1]$ ，然后再比较 $pattern[j - 1]$ 与 $pattern[next[k]]$ ，直到 $k == -1$ 或者 $pattern[j - 1] == pattern[next[k]]$ ，对于后者，我们就令 $next[j] == next[k] + 1$。因为相同前缀的子串在模式串中可能多次出现，之前的 $next$ 值记录的可能是靠后的前缀子串的位置，所以我们需要递归查找直到所有相同前缀子串遍历完成。
从而KMP算法的实现为：

public class KMP {
    public static int search(String pat, String txt) {
        int M = pat.length();
        int N = txt.length();
        int[] next = getNext(pat, N);
        int i = 0, j = 0;
        while (i < M && j < N) {
            if (j == -1 || txt.charAt(i) == pat.charAt(j)) {
                i++;
                j++;
            } else j = next[j];
        }
        return j == N ? i - j : -1;
    }

    private static int[] getNext(String pat, int N) {
        int[] next = new int[N];
        next[0] = -1;
        int k = -1, j = 0;
        while (j < N - 1) {
            if (k == -1 || pat.charAt(j) == pat.charAt(k)) {
                k++;
                j++;
                next[j] = k;
            } else k = next[k];
        }
        return next;
    }
}

至此已经完成了KMP算法，但是还存在着一个问题，举个例子，对于字符串 $ABACABABC$ 和模式串 $ABAB$ ，可以得出 $next[\ ] = \{-1, 0, 0, 1\}$ 。然后进行匹配，直到第 $4$ 个字符，此时 $txt[3] = “C”$ ，$pat[3] = “B”$ ，于是 $txt[3] != pat[3]$ ，查找得出 $j = next[3] = 1$ ，于是又重新比对 $txt[3]$ 和 $pat[1]$ 。显然最后一步是没有必要的，因为我们已经知道 $txt[3] != “B”$ 了。所以我们可以对原来的 $next[\ ]$ 数组进行优化：

public static int[] getNextVal(String pat, int N) {
    int[] nextVal = new int[N];
    nextVal[0] = -1;
    int k = -1, j = 0;
    while (j < N - 1) {
        if (k == -1 || pat.charAt(j) == pat.chatAt(k)) {
            j++;
            k++;
            if (pat.charAt(j) != pat.charAt(k)) nextVal[j] = k;
            else nextVal[j] = nextVal[k];
        } else k = nextVal[k];
    }
    return nextVal;
}

实现思路很简单，就是在每次递增后判断当前字符是否与 $next$ 值相等，如果相等，就递归 $next$ 值。

String.indexOf方法和KMP算法简介

回到顶部

String.indexOf方法和KMP算法简介

1. String.indexOf

2. KMP

1. `String.indexOf`

2. `KMP`