Java字符串搜索思想（String）

今天被问到Java字符串搜索，中午抽空研究了String的源码。

 

int indexOf(String str)

 

核心查找代码：

 

        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;
                }
            }
        }

 

这段代码的简单思想是：从源字符串的索引0开始，按字符查找，直到最大索引max（max=源字符串长度 - 子字符串长度），找到和子串第一个字符（first）匹配的字符，记下索引位置并且存放到变量i中；

 

接下去判断i是否超出max，如果超出，则直接返回-1，查找结束；

 

如果i小于max，则源字符串索引i加1，子字符串索引k也加1，然后比对这两个索引对应的字符：

如果相等，两个字符串的索引再各自加1继续循环；

如果不相等，跳出循环；

 

继续执行下面的代码： 如果j==end意味着子串遍历完了（也就是在源字符串查找到了子串），返回查找到的子串索引，程序结束；

 

如果不满足j==end，则源字符串的索引i++，然后重新执行上面过程，直到源字符串遍历到最大索引max（这中间可能找到子串，提前返回）；

 

这种字符串查找的算法谈不上高效，但是对于小字符串来说应该够用了；

 

对于字符串查找场景较多，并且字符串很长的情况（可能需要查找的子串靠近源字符串的后半部分），这个方法可能效率不够高；

 

 接着写 int lastIndexOf(String str)，先上源码：

 

        int strLastIndex = targetOffset + targetCount - 1;
        char strLastChar = target[strLastIndex];
        int min = sourceOffset + targetCount - 1;
        int i = min + fromIndex;

        startSearchForLastChar:
        while (true) {
            while (i >= min && source[i] != strLastChar) {
                i--;
            }
            if (i < min) {
                return -1;
            }
            int j = i - 1;
            int start = j - (targetCount - 1);
            int k = strLastIndex - 1;

            while (j > start) {
                if (source[j--] != target[k--]) {
                    i--;
                    continue startSearchForLastChar;
                }
            }
            return start - sourceOffset + 1;
        }

 

 

 

查找的原理大致和indexOf相同，只不过lastIndexOf是从尾部开始查找的，并且中间的一些细节还是和indexOf不同的。

 

上面这段代码的主要意思是：

初始计算部分：

 计算子串的最后一个字符，存入变量strLastChar中；

计算源字符串查找的终点索引，存入变量min；

计算源字符串的查找起点索引，存入变量i；

 

进入第一个while循环：

           while (i >= min && source[i] != strLastChar) {
                i--;
            }

 这段代码是在源字符串找到和子串最后一个字符相等的字符，把他的索引存入变量i（从尾部开始查找）

 

如果索引i小余min，意味着已经不在上面规定的查找范围之内了，直接返回-1；

如果索引i合法，那么确定源字符串的查找范围（起点j=i-1，终点start=起点-子串长度+1）【源码中终点的变量是start，作者觉得这是查找的终点，请注意区分】

确定子串的查找起点k=子串最后一个字符索引-1

用源字符串的索引j处的字符和子串索引k处的字符比较，并且j和k各自减1：

如果字符相等，则继续执行上面的比较，直到索引j递减到j>start（索引j超出了查找的终点start），则跳出循环继续往下执行；

如果字符不相等，则程序跳转到锚点startSearchForLastChar处，按照上面的逻辑继续执行；

 

如果if (source[j--] != target[k--])的比对一直相等，并且把while (j > start)循环执行完了，意味着在源字符串找到了子串（只需要找到第一个就可以了，当然是从末尾开始找的），程序返回子串的索引。

 

对于很长的字符串查找的优化，推荐一篇文章： KMP子字符串查找算法分析与实现

 

全文完。