长字符串中检测短字符串的出现次数(四)-阿里云开发者社区

一. 题目的解释

有一个长字符串，如"abcdabbababbababbab",检测子字符串"ab" 在这个长字符串中出现的次数。

判断一个字符串里面是否包含，或者含有另外一个字符串，可以用contains() 方法和indexOf() 方法，但contains() 方法，只返回一个boolean 的状态值，不能记录出现的位置，所以可以用indexOf() 来进行相应的判断。

二. contains()方法和indexOf() 方法

其中，contains() 方法是:

public boolean contains(CharSequence s) {
  //内部调用的是indexOf()的方法。
        return indexOf(s.toString()) > -1;
    }

其中,indexOf() 方法重载了多种形式，也有一个变体， lastIndexOf()

其中，主要有四种变体，一种是从头开始查询，即indexOf(), 另外一种是从尾开始查询，即lastIndexOf(), 一种传入的是 int 类型，另外一种传入的是 String 字符串形式。

二.一 indexOf(int) 形式

如果没有开始位置 fromIndex :

public int indexOf(int ch) {
    // 会默认从0 开始查询，调用有开始位置的方法
        return indexOf(ch, 0);
    }

有开始位置的方法:

 public int indexOf(int ch, int fromIndex) {
    // 取当前字符串的最大长度
        final int max = value.length;
        // 如果传入的开始位置< 0,即为0 或者是为负数，那么就处理成0
        if (fromIndex < 0) {
            fromIndex = 0;
        } else if (fromIndex >= max) { // 如果大于等于最大的长度，就返回-1. formIndex的范围是0~max-1
            // Note: fromIndex might be near -1>>>1.
            return -1;
        }
  // 判断，如果是普通的数字，小于 65536,unicode 的编码是两个字节，最大为65536
        if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
            // handle most cases here (ch is a BMP code point or a
            // negative value (invalid code point))
            //拆分成字符数组
            final char[] value = this.value;
            for (int i = fromIndex; i < max; i++) {
              // 如果相同，返回 i的索引值。
                if (value[i] == ch) {
                    return i;
                }
            }
            return -1;
        } else {
        // 进行特殊值的查询，即>65536的时候的方法
            return indexOfSupplementary(ch, fromIndex);
        }
    }

 private int indexOfSupplementary(int ch, int fromIndex) {
    // 小于字符的最大值， 0X10FFFF 这个数时，还能比较
        if (Character.isValidCodePoint(ch)) {
        //字符数组
            final char[] value = this.value;
            // 高代码
            final char hi = Character.highSurrogate(ch);
            final char lo = Character.lowSurrogate(ch);
            //该对象字符串的长度
            final int max = value.length - 1;
            for (int i = fromIndex; i < max; i++) {
              //相同，就返回i , 这个相同是什么意思，不知道，猜想是大数的一种处理形式。 没有找到，返回-1
                if (value[i] == hi && value[i + 1] == lo) {
                    return i;
                }
            }
        }
        //如果大于 0X10FFFF, 则不能比较了，直接返回-1
        return -1;
    }

public static char highSurrogate(int codePoint) {
        return (char) ((codePoint >>> 10)
          //\ud800    0x10000即65536
            + (MIN_HIGH_SURROGATE - (MIN_SUPPLEMENTARY_CODE_POINT >>> 10)));
    }

public static char lowSurrogate(int codePoint) {
  // \uDC00
        return (char) ((codePoint & 0x3ff) + MIN_LOW_SURROGATE);
    }

二.二 lastIndexOf(int)

没有开始位置的，会设置默认的位置为最后一个。调用有开始位置的方法.

  public int lastIndexOf(int ch) {
        return lastIndexOf(ch, value.length - 1);
    }

有开始位置的方法: 其中，返回的值只能 <=formIndex的值

  public int lastIndexOf(int ch, int fromIndex) {
  // 65536
        if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {
            // handle most cases here (ch is a BMP code point or a
            // negative value (invalid code point))
            final char[] value = this.value;
            //最小值， 如果formIndex 传入的值> 最大值，那么就为最后的位置。 如果<最大值，那么就是当前的formIndex的位置。  判断formIndex <0 的情况, 返回的是-1
            int i = Math.min(fromIndex, value.length - 1);
            for (; i >= 0; i--) {
                if (value[i] == ch) {  //如果相同， 返回i,不相同返回-1
                    return i;
                }
            }
            return -1;
        } else {
        // >65536时
            return lastIndexOfSupplementary(ch, fromIndex);
        }
    }

private int lastIndexOfSupplementary(int ch, int fromIndex) {
    // 与indexOf(int) 一样，都是不懂。
        if (Character.isValidCodePoint(ch)) {
            final char[] value = this.value;
            char hi = Character.highSurrogate(ch);
            char lo = Character.lowSurrogate(ch);
            // 求最小的值,此时判断为length-2
            int i = Math.min(fromIndex, value.length - 2);
            for (; i >= 0; i--) {
                if (value[i] == hi && value[i + 1] == lo) {
                    return i;
                }
            }
        }
        return -1;
    }

二.三测试 indexOf(int) 和lastIndexOf(int)

@Test
  public void testA(){
    System.out.println("abcd".indexOf(98)); //1  98的unicode码是b
    System.out.println("abcd".indexOf(98,2)); // -1
    System.out.println("abcd".lastIndexOf(98)); //1
    System.out.println("abcd".lastIndexOf(98,2)); //返回的结果只能是小于fromIndex
  }

二.四 indexOf(String)

没有传入开始位置的，默认开始位置为0

 public int indexOf(String str) {
        return indexOf(str, 0);
    }

有参数位置的,将当前字符串，开始位置，验证的长度，目标字符串，目标的位置，

目标的长度，还有起始位置传入进去:

 public int indexOf(String str, int fromIndex) {
        return indexOf(value, 0, value.length,
                str.value, 0, str.value.length, fromIndex);
    }

这个目标的方法，不太好解释，也不容易理解，可以举例子进行相应的说明。

如: 传入参数为:

indexOf("abcdefghijklmn".toCharArray(),
            1, 10,"cdefg".toCharArray(),1,2, 1)

  // 传入的参数是 abcdefghijklmn 1 10 cdefg 1 2 1
  public static int indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset,
      int targetCount, int fromIndex) {
    if (fromIndex >= sourceCount) { // 比截取后的源字符串长， 如果目标字符串的长度==0,
      // 返回源字符串的数目，否则返回-1. 即比较的是""是返回sourceCount,否则是-1
      return (targetCount == 0 ? sourceCount : -1);
    }
    if (fromIndex < 0) { // 为负数时，处理成0的情况。
      fromIndex = 0;
    }
    if (targetCount == 0) { // 如果目标的长度是0,即比较的是"" 时，返回fromIndex
      return fromIndex;
    }
    // 为target[1]=d
    char first = target[targetOffset]; // 目标字符串最开始的字符
    // 最大是:1+(10-2)=9 ,也就是比较的时候，并不是比较完，只比较到1+10=11 -2=9，即-目标数目处。
    int max = sourceOffset + (sourceCount - targetCount);
    // 从源字符串的起始位置+formIndex处开始，即从1+1=2 c处开始。 为9
    for (int i = sourceOffset + fromIndex; i <= max; i++) {
      /* Look for first character. */
      if (source[i] != first) { // 现在当前位置为c,不为d,还差一点，需要先移动
        // 到d 处。 即 令i++, 但要保证i<=max 并且 不相同。 如果相同，就 ; 跳出了循环。
        while (++i <= max && source[i] != first)
          ;
      }
      // 现在i 已经到达了d 处，即i=3
      /* Found first character, now look at the rest of v2 */
      if (i <= max) { // <=9时,
        int j = i + 1; // j=4 时, e处
        // 4+2-1=5 结束的点。 f处。
        int end = j + targetCount - 1;
        // 从1+1=2 处开始，从c 开始, 到f处为止并且 资源[j]==目标的k 时,j++,k++
        for (int k = targetOffset + 1; j < end && source[j] == target[k]; j++, k++)
          ;
        /**
         * k=1+1=2 ,c处。 j=4 < 5, 并且 source[4]=e == target[2]=e ==> j=5
         * k=3 j=5<5 不符合条件，退出循环。
         */
        // 其中 j=5=5, 相同,找到了。
        if (j == end) {
          /* Found whole string. */
          // 返回3-1=2 处。
          return i - sourceOffset;
        }
      }
    }
    // 否则，即j !==end 时，返回-1
    return -1;
  }

其实，这个方法表明的主要意思是什么呢，可以简单理解成:

// 传入的参数是 abcdefghijklmn 1 10 cdefg 1 2 1
  public static int indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset,
      int targetCount, int fromIndex) {
    //1.将 源字符数组封装成String 字符串
    String sourceString=new String(source);
    //2. 将源字符串进行相应的拆分，找到真正的源数据。
    sourceString=sourceString.substring(sourceOffset,sourceOffset+sourceCount);
    System.out.println("sourceString:"+sourceString); //bcdefghijk
    //3 将目标字符数组封装成String 字符串
    String targetString=new String(target);
    //4 将目标字符串进行相应的拆分，找到真正的源数据。
    targetString=targetString.substring(targetOffset,targetOffset+targetCount);
    System.out.println("targetString:"+targetString); //de
    //5. 实际上就变成了 sourceString 与targetString 在fromIndex 处的比较
    return sourceString.indexOf(targetString,fromIndex);
  }

二.五 lastIndexOf()

public int lastIndexOf(String str) {
    // 默认从最大长度处开始
        return lastIndexOf(str, value.length);
    }

public int lastIndexOf(String str, int fromIndex) {
    //转换成数组
        return lastIndexOf(value, 0, value.length,
                str.value, 0, str.value.length, fromIndex);
    }

 static int lastIndexOf(char[] source, int sourceOffset, int sourceCount,
            char[] target, int targetOffset, int targetCount,
            int fromIndex) {
        /*
         * Check arguments; return immediately where possible. For
         * consistency, don't check for null str.
         */
        int rightIndex = sourceCount - targetCount;
        if (fromIndex < 0) {
            return -1;
        }
        if (fromIndex > rightIndex) {
            fromIndex = rightIndex;
        }
        /* Empty string always matches. */
        if (targetCount == 0) {
            return fromIndex;
        }
        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() 一样，可以简单理解成:

// 传入的参数是 abcdefghijklmn 1 10 cdefg 1 2 10  返回结果为2
  public static int lastIndexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset,
      int targetCount, int fromIndex) {
    //1.将 源字符数组封装成String 字符串
    String sourceString=new String(source);
    //2. 将源字符串进行相应的拆分，找到真正的源数据。
    sourceString=sourceString.substring(sourceOffset,sourceOffset+sourceCount);
    System.out.println("sourceString:"+sourceString); //bcdefghijk
    //3 将目标字符数组封装成String 字符串
    String targetString=new String(target);
    //4 将目标字符串进行相应的拆分，找到真正的源数据。
    targetString=targetString.substring(targetOffset,targetOffset+targetCount);
    System.out.println("targetString:"+targetString); //de
    //5. 实际上就变成了 sourceString 与targetString 在fromIndex 处的比较
    return sourceString.lastIndexOf(targetString,fromIndex);
  }

二.六测试

@Test
  public void test2(){
    System.out.println("abcdef".indexOf("cd")); //2 
    System.out.println("abcdef".indexOf("cd",4)); //-1 
    System.out.println("abcdef".indexOf("cd",10)); //-1
    System.out.println("abcdef".indexOf("cd",-2)); //2 会将-2处理成0
    System.out.println("abcdef".lastIndexOf("cd")); //2
    System.out.println("abcdef".lastIndexOf("cd",4)); //2
    System.out.println("abcdef".lastIndexOf("cd",10)); //2
    System.out.println("abcdef".lastIndexOf("cd",-2)); //-1  会将-2处理成0
    // 对于传入字符数组的源代码形式，并不能进行访问
  }

三. 第一种方式对字符串进行截取处理

利用indexOf(string) 方法

  // 传入参数为 abcdabbababbababbab  ab
  public static int getShowCount1(String showStr,String subString){
    StringBuilder sbBuilder=new StringBuilder(showStr);
    //要看是否包含。 可以用contain和indexOf来判断。 但不需要知道出现的位置，方便下一次的搜索。
    //用indexOf. 不知道具体多少次，用while. 当为-1时，表示没有了。
    int count=0;
    int index=0;
    // 有值的情况下
    while((index=sbBuilder.indexOf(subString))!=-1){
      //重新进行下一次的循环。 对长字符进行相关的验证，将前端已经出现的去除掉。
      // 这个时候，showStr 第一次循环变成了  cdabbababbababbab  ab 继续传入   count++
      // 第二次循环时，变成了bababbababbab ab count++
      // 第三次循环时, 变成了abbababbab ab count++   依次继续，会源数据进行相应的操作
      sbBuilder.substring(index+subString.length());
      count++;
    }
    return count;
  }

四.第二种方式，利用indexOf(Strng,fromIndex) 方法

// 传入参数为 abcdabbababbababbab  ab
  public static int getShowCount2(String showStr,String subString){
    //要看是否包含。 可以用contain和indexOf来判断。 但contains不需要知道出现的位置，方便下一次的搜索。
    //用indexOf. 不知道具体多少次，用while. 当为-1时，表示没有了。
    int count=0;
    int sublength=subString.length();
    int index=-sublength;  //从哪个开始。 自然是从0开始,将index的初始值默认为-sublength
    while((index=showStr.indexOf(subString,index+sublength))!=-1){
      // 不断的改变fromIndex的值
      count++;
    }
    return count;
  }

结果为7

谢谢!!!

长字符串中检测短字符串的出现次数(四)

二.一 indexOf(int) 形式

二.二 lastIndexOf(int)

二.三测试 indexOf(int) 和lastIndexOf(int)

二.四 indexOf(String)

二.五 lastIndexOf()

二.六测试

三. 第一种方式对字符串进行截取处理

四.第二种方式，利用indexOf(Strng,fromIndex) 方法

热门文章

最新文章

相关电子书

长字符串中检测短字符串的出现次数(四)

二.一 indexOf(int) 形式

二.二 lastIndexOf(int)

二.三 测试 indexOf(int) 和lastIndexOf(int)

二.四 indexOf(String)

二.五 lastIndexOf()

二.六 测试

三. 第一种方式 对字符串进行截取处理

四.第二种方式， 利用indexOf(Strng,fromIndex) 方法

热门文章

最新文章

相关电子书

二.三测试 indexOf(int) 和lastIndexOf(int)

二.六测试

三. 第一种方式对字符串进行截取处理

四.第二种方式，利用indexOf(Strng,fromIndex) 方法