字符串匹配算法从indexOf函数讲起

2022-03-30 23:56:40

前言

相信每个学习过Java的人都使用过indexOf函数，indexOf函数我们可以查找一个字符串（模式串）是否在另一个字符串（主串）出现过，返回结果表示出现位置的下标，如果返回-1，表示模式串在主串中不存在，那么，你可曾想过这些查找函数又是如何实现的呢？

从indexOf源码看起

首先我们先来看一下indexOf的源码，indexOf的使用方式比较多，这是我们以一个形参的为例。

static String mainString = "Hello my name is HuangLinqing";
static String patternString = "HuangLinqing";
public static void main(String[] args) {
    System.out.printf(mainString.indexOf(patternString, 0) + "");
}

运行上面代码的结果，返回的结果是17，说明模式串在主串中存在，并且第一次出现的位置下标是17

indexOf方法最终会走到下面方法中，源码如下所示:

/**
 * Code shared by String and StringBuffer to do searches. The
 * source is the character array being searched, and the target
 * is the string being searched for.
 *
 * @param   source       the characters being searched.
 * @param   sourceOffset offset of the source string.
 * @param   sourceCount  count of the source string.
 * @param   target       the characters being searched for.
 * @param   targetOffset offset of the target string.
 * @param   targetCount  count of the target string.
 * @param   fromIndex    the index to begin searching from.
 */
static int indexOf(char[] source, int sourceOffset, int sourceCount,
        char[] target, int targetOffset, int targetCount,
        int fromIndex) {
    if (fromIndex >= sourceCount) {
        return (targetCount == 0 ? sourceCount : -1);
    }
    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++) {
        /* Look for first character. */
        if (source[i] != first) {
            while (++i <= max && source[i] != first);
        }
        /* Found first character, now look at the rest of v2 */
        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) {
                /* Found whole string. */
                return i - sourceOffset;
            }
        }
    }
    return -1;
}

代码行数不多，接下来我们来分析一下，上面的代码，fromIndex默认是0,target是模式串，targetCount是模式串的大小，source是主串，sourceCount是主串的大小

if (fromIndex >= sourceCount) {
    return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
    fromIndex = 0;
}
if (targetCount == 0) {
    return fromIndex;
}

如果开始查找的位置大于主串的大小，如果模式串是空串就返回主串的大小，否则返回-1，如果模式串的大小等于0就是开始查找的位置，这几行代码很好理解，就不举例子了，主要是下面的代码：

char first = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
    /* Look for first character. */
    if (source[i] != first) {
        while (++i <= max && source[i] != first);
    }
    /* Found first character, now look at the rest of v2 */
    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) {
            /* Found whole string. */
            return i - sourceOffset;
        }
    }
}

indexOf底层使用的方法是典型的BF算法，我们先来简单介绍BF算法，再回过头来理解上面的代码就比较容易了

BF与RK算法

BF算法

BF算法就是Brute Force，暴力匹配算法，也成为朴素匹配算法，主串的大小是sourceSize，模式串的大小是targetSize，因为我们要在主串中查找模式串，所以sourceZize > targetSize,所以从主串下标为0开始，连续查找targetSize个字符，再从下标为1开始后，一直到，下标为sourceSize - targetSize ,举个简单的例子在ABCDEFG中查找EF：

上图依次表示从i为0，到i为4时的依次比较，从图中我们也可以看出，BF算法是比较耗时的，因为比较的次数较多，但是实际比较的时候主串和模式串都不会太长，所以这种比较的方法更容易使用。

现在我们回过头看看indexOf的下半部分源码，我相信其实不用解释了。

RK算法

RK算法其实就是对BF算法的升级，还是以上面的图为例，在ABCDEFG中查找EF的时候，比如下标为0的时候，我们去比较A和E的值，不相等就不继续往下比较了，但是比如我们现在查找CDF是否在主串中存在，我们要从C已知比较大E发现第三位不相等，这样当模式串前一部分等于主串，只有最后一位不相等的时候，比较的次数太多了，效率比较低，所以我们可以采用哈希计算来比较，哈希计算 后面我会补充一篇。

我们要将模式串和sourceSize - targetSize + 1 个字符串相比，我们可以先将sourceSize - targetSize + 1个模式串进行哈希计算。与哈希计算后的模式串相比较，如果相等则存在，对于哈希冲突在一般实现中概率比较低，不放心的话我们可以在哈希值相等时候再比较一次原字符串确保准确，哈希的冲突概率也和哈希算法的本身设计有关。这样的话，我们首先计算AB的哈希值与模式串的相比较，然后计算BC的哈希值与模式串相比较，直到比较出相等的返回下标即可。

码农公寓

前言

从indexOf源码看起

BF与RK算法

相关文章