一、java实现查找字符串在文本出现的次数

每日记录分析一个小算法

第一种实现方式

中心思想：不断的去切割文本去匹配第一个符合条件的字符串

代码如下

  private static int strAppearInTextCount(String sourceStr, String findStr) {
        int count = 0;
        while (true) {
            //获取文本中第一个匹配的字符串的位置
            int index = sourceStr.indexOf(findStr);
            //index=-1代表没有匹配到
            if (index != -1) {
                //每次都对sourceStr截取，从上一次找到的字符串末尾位置开始截取
                sourceStr = sourceStr.substring(index + findStr.length());
                count++;
            } else {
                break;
            }
        }
        return count;
    }

时间复杂度：

假设文本出现的次数是m次，文本的长度是n，匹配的字符服串的长度是k，时间复杂度是O（m* n* k），其中n *k是indexof（）方法中消耗的时间复杂度咱们可以看下源码如下

 static int indexOf(String source,
                       String target,
                       int fromIndex) {
        final int sourceLength = source.length();
        final int targetLength = target.length();
        if (fromIndex >= sourceLength) {
            return (targetLength == 0 ? sourceLength : -1);
        }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        if (targetLength == 0) {
            return fromIndex;
        }

        char first = target.charAt(0);
        int max = (sourceLength - targetLength);

        for (int i = fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source.charAt(i)!= first) {
                while (++i <= max && source.charAt(i) != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetLength - 1;
                for (int k = 1; j < end && source.charAt(j)
                         == target.charAt(k); j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i;
                }
            }
        }
        return -1;
    }
    

可以看出java 源码中匹配字符串是遍历一个个字符查找的

空间复杂度：

假设文本出现的次数是m次，文本的长度是n，匹配的字符服串的长度是k，每次文本截取的时候都会subString（）然后赋值，因为java字符串的不可变性，每次赋值都会重新申请一片内存。空间复杂度是O（m）

第二种实现方式

中心思想：优化字符串赋值导致消耗内存的问题，

可以利用indexof（）的重载方法，indexof（str，fromIndex）第二个参数是从该位置开始匹配字符串，每次更新这个参数即可
代码如下

    private static int strAppearInTextCount(String sourceStr, String findStr) {
        int count = 0;
        int index = 0;
        while (true) {
            //判断是不是没有符合条件的字符串了
            if (index != -1) {
                //每次更新下次要检索的位置起点，它等于上一次匹配的字符串的结束位置
                index = sourceStr.indexOf(findStr, index) + findStr.length();
                count++;
            } else {
                break;
            }
        }
        return count;
    }

时间复杂度：O(m *n * k) 空间复杂度O(1)

第三种实现方式

中心思想：KMP算法 可以将indexof()时间复杂度优化至O（n）

不足之处希望大家指出