首页  

java String indexOf 为何不使用KMP     所属分类 algo 浏览量 48
字符串匹配算法

Broute-Force(暴力查找)实现简单且在一般情况下工作良好(Java String indexOf 使用BF算法)
KMP Knuth-Morris-Pratt 算法设计巧妙但复杂,能够保证最坏情况下也是线性级别的性能,且不需要回退文本串指针
Boyer-Moore 算法的性能在一般情况下都是亚线性级别(可能是线性级别的M倍),且对于越长的模式串其速度可能会越快
Rabin-Karp 算法的内循环不同于前面三种算法,它的内循环的主要工作是计算哈希值,RK算法还支持多模式匹配

JDK编写者们认为大多数情况下,字符串都不长,使用原始实现可能代价更低
KMP和Boyer-Moore算法都需要预先计算处理来获得辅助数组 
需要一定的时间和空间,在短字符串查找中可能耗费更大的代价
一般大字符串查找时,会使用其它特定的数据结构 

https://stackoverflow.com/questions/19543547/why-does-string-indexof-not-use-kmp


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

上一篇     下一篇
数据结构中的各种树

树的定义和术语

算法基础知识

AVL树与红黑树(RBTree)

aerospike lua udf 例子

计算机专业考研信息