黑马程序员技术交流社区

标题: 字符串中查找子串的原理分析（即String类中的indexOf()） [打印本页]
作者: Ralap军    时间: 2015-9-10 00:23
标题: 字符串中查找子串的原理分析（即String类中的indexOf()）
本帖最后由 Ralap军 于 2015-9-10 00:23 编辑

今天学到String类的各种功能方法，对indexOf()的原理产生了兴趣，就去研究了一番源码。思路：
1、排除异常的比较数据。这里写的很严谨，应多向作者学习
2、遍历源字符数组，循环查找与目标数组第一个字符相同的位置
3、若遍历完都没有找到，就退出循环，返回-1
     若找到了，则对剩下的字符数组进行匹配。全部匹配成功，则返回索引值，否则重复第2步

以下是源码，写了一些注释说明
  1. static int indexOf(char[] source, int sourceOffset, int sourceCount,
  2.                         char[] target, int targetOffset, int targetCount, int fromIndex) {
  3.                 if (fromIndex >= sourceCount) { // 如果索引值超过了源字符数组的长度
  4.                         return (targetCount == 0 ? sourceCount : -1); // 如果目标字符数组长度为0，返回源字符数组长度，否则返回-1
  5.                 }
  6.                 if (fromIndex < 0) { // 如果开始索引值小于0，把开始索引值设为0
  7.                         fromIndex = 0;
  8.                 }
  9.                 if (targetCount == 0) { // 如果目标字符长度为0，返回开始索引值
  10.                         return fromIndex;
  11.                 }

  13.                 char first = target[targetOffset]; // 获取目标字符数组的第一个字符
  14.                 int max = sourceOffset + (sourceCount - targetCount);// 索引的在源字符数组中能得到的最大值

  16.                 for (int i = sourceOffset + fromIndex; i <= max; i++) { //遍历源字符数组
  17.                         
  18.                         /* Look for first character. */
  19.                         /* 查找目标字符数组第一个字符在源字符数组中第一次出现的位置
  20.                          * 可用此语句代替：while(source[i] != first && ++i <= max);
  21.                          */
  22.                         if (source[i] != first) {
  23.                                 while (++i <= max && source[i] != first);
  24.                         }

  26.                         /* Found first character, now look at the rest of v2 */
  27.                         if (i <= max) { // 如果在源字符数组中找到了第一个字符
  28.                                 int j = i + 1;  // 从下一个字符开始继续匹配
  29.                                 int end = j + targetCount - 1; // 从开始值开始，匹配目标中剩下的targetCount-1个字符
  30.                                 for (int k = targetOffset + 1; j < end && source[j] == target[k]; j++, k++); // 源数组循环与目标匹配
  31.                                 if (j == end) { //如果全部匹配，返回对应的索引值
  32.                                         /* Found whole string. */
  33.                                         return i - sourceOffset;
  34.                                 }
  35.                         }
  36.                 }
  37.                 return -1;
  38.         }
复制代码
后根据她的思想，自己写了一个简单字符串查找方法
  1.         static int indexOf_2(String src, String tag, int offset) {
  2.                 final int srcLen = src.length();
  3.                 final int tagLen = tag.length();
  4.                 if (srcLen == 0 || tagLen == 0 ||  tagLen > srcLen  || offset > srcLen ) {
  5.                         return -1;
  6.                 }
  7.                 if (offset < 0) {
  8.                         offset = 0;
  9.                 }
  10.                 int max = srcLen - tagLen;
  11.                 for (int i = offset; i <= max; i++) {
  12.                         while ((src.charAt(i) != tag.charAt(0)) && (++i <= max));
  13.                         int k = 1;
  14.                         for (int j = i + 1; k < tagLen && src.charAt(j) == tag.charAt(k); j++, k++);
  15.                         if (k == tagLen) {
  16.                                 return i;
  17.                         }
  18.                 }
  19.                 return -1;
  20.         }
复制代码
测试代码：
  1. String string = "bnnbacnbaa";
  2. System.out.println(indexOf_2(string, "nba", 0));
复制代码

里面最经典的就数while和for循环了。值得好好研究，并学以致用。







欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2