个人中心
gpt4 book ai didi

浅谈JAVA字符串匹配算法indexOf函数的实现方法

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章浅谈JAVA字符串匹配算法indexOf函数的实现方法由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

前言 。

相信每个学习过Java的人都使用过indexOf函数，indexOf函数我们可以查找一个字符串（模式串）是否在另一个字符串（主串）出现过，返回结果表示出现位置的下标，如果返回-1，表示模式串在主串中不存在，那么，你可曾想过这些查找函数又是如何实现的呢?

浅谈JAVA字符串匹配算法indexOf函数的实现方法

从indexOf源码看起 。

首先我们先来看一下indexOf的源码，indexOf的使用方式比较多，这是我们以一个形参的为例.

?
1
2
3
4
5
6
static String mainString = "Hello my name is HuangLinqing" ;
static String patternString = "HuangLinqing" ;
 
public static void main(String[] args) {
  System.out.printf(mainString.indexOf(patternString, 0 ) + "" );
}

运行上面代码的结果，返回的结果是17，说明模式串在主串中存在，并且第一次出现的位置下标是17 。

indexOf方法最终会走到下面方法中，源码如下所示

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
  * Code shared by String and StringBuffer to do searches. The
  * source is the character array being searched, and the target
  * is the string being searched for.
  *
  * @param source the characters being searched.
  * @param sourceOffset offset of the source string.
  * @param sourceCount count of the source string.
  * @param target the characters being searched for.
  * @param targetOffset offset of the target string.
  * @param targetCount count of the target string.
  * @param fromIndex the index to begin searching from.
  */
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 ;
}

代码行数不多，接下来我们来分析一下，上面的代码，fromIndex默认是0,target是模式串，targetCount是模式串的大小，source是主串，sourceCount是主串的大小 。

?
1
2
3
4
5
6
7
8
9
if (fromIndex >= sourceCount) {
  return (targetCount == 0 ? sourceCount : - 1 );
}
if (fromIndex < 0 ) {
  fromIndex = 0 ;
}
if (targetCount == 0 ) {
  return fromIndex;
}

如果开始查找的位置大于主串的大小，如果模式串是空串就返回主串的大小，否则返回-1，如果模式串的大小等于0就是开始查找的位置，这几行代码很好理解，就不举例子了，主要是下面的代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
  }
  }
}

indexOf底层使用的方法是典型的BF算法，我们先来简单介绍BF算法，再回过头来理解上面的代码就比较容易了 。

BF与RK算法 。

BF算法 。

BF算法就是Brute Force，暴力匹配算法，也成为朴素匹配算法，主串的大小是sourceSize，模式串的大小是targetSize，因为我们要在主串中查找模式串，所以sourceZize > targetSize,所以从主串下标为0开始，连续查找targetSize个字符，再从下标为1开始后，一直到，下标为sourceSize - targetSize ,举个简单的例子在ABCDEFG中查找EF:

浅谈JAVA字符串匹配算法indexOf函数的实现方法

上图依次表示从i为0，到i为4时的依次比较，从图中我们也可以看出，BF算法是比较耗时的，因为比较的次数较多，但是实际比较的时候主串和模式串都不会太长，所以这种比较的方法更容易使用.

现在我们回过头看看indexOf的下半部分源码，我相信其实不用解释了.

RK算法 。

RK算法其实就是对BF算法的升级，还是以上面的图为例，在ABCDEFG中查找EF的时候，比如下标为0的时候，我们去比较A和E的值，不相等就不继续往下比较了，但是比如我们现在查找CDF是否在主串中存在，我们要从C已知比较大E发现第三位不相等，这样当模式串前一部分等于主串，只有最后一位不相等的时候，比较的次数太多了，效率比较低，所以我们可以采用哈希计算来比较，哈希计算 后面我会补充一篇.

我们要将模式串和sourceSize - targetSize + 1 个字符串相比，我们可以先将sourceSize - targetSize + 1个模式串进行哈希计算。与哈希计算后的模式串相比较，如果相等则存在，对于哈希冲突在一般实现中概率比较低，不放心的话我们可以在哈希值相等时候再比较一次原字符串确保准确，哈希的冲突概率也和哈希算法的本身设计有关。这样的话，我们首先计算AB的哈希值 与 模式串的相比较，然后计算BC的哈希值与模式串相比较，直到比较出相等的返回下标即可.

到此这篇关于浅谈字符串匹配算法从indexOf函数的实现方法的文章就介绍到这了,更多相关字符串匹配算法从indexOf函数的实现方法内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。

原文链接：https://blog.csdn.net/huangliniqng/article/details/103677768 。

最后此篇关于浅谈JAVA字符串匹配算法indexOf函数的实现方法的文章就讲到这里了,如果你想了解更多关于浅谈JAVA字符串匹配算法indexOf函数的实现方法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

26 4 0
文章推荐： php metaphone()函数及php localeconv() 函数实例解析
文章推荐： 非常实用的php验证码类
文章推荐： thinkphp框架下404页面设置 仅三步
文章推荐： Java实现读取及生成Excel文件的方法
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com