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

2024-11-28 18:49:37

前言

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

从indexOf源码看起

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

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方法最终会走到下面方法中，源码如下所示:

/**
 * 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是主串的大小

if (fromIndex >= sourceCount) {
 return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
 fromIndex = 0;
}
if (targetCount == 0) {
 return fromIndex;
}

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

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：

上图依次表示从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函数的实现方法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

PHP实现的字符串匹配算法示例【sunday算法】

本文实例讲述了PHP实现的字符串匹配算法----sunday算法.分享给大家供大家参考,具体如下: Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配.其核心思想是:在匹配过程中,模式串发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率. <?php /* *@param $pattern 模式串 *@param $text 待匹配串 */ function mySunday($pattern = '',$text = ''){ if(!$
php中最简单的字符串匹配算法

本文实例讲述了php中最简单的字符串匹配算法.分享给大家供大家参考.具体实现方法如下: 复制代码代码如下: <?php /* 最简单字符串匹配算法php实现方式 T: ababcabc P: abc 0. 1. 2. ababcabc ababcabc ababcabc ||| ||| ||| abc abc abc (X) (X)
javascript indexOf函数使用说明

使用方法:strObj.indexOf(str,startIndex[可选]) 程序代码其中strObj是必选项.String 对象或文字. str是必选项.要在 String 对象中查找的子字符串. startIndex是可选项.该整数值指出在 String 对象内开始查找的位置,从0开始.如果省略,则从字符串的开始处查找. 注意:对于JavaScript的indexOf是区分大小写的. JavaScript中indexOf函数方法返回一个整数值,指出 String 对象内子字符串的开始位置
Python字符串匹配算法KMP实例

本文实例讲述了Python字符串匹配算法KMP.分享给大家供大家参考.具体如下: #!/usr/bin/env python #encoding:utf8 def next(pattern): p_len = len(pattern) pos = [-1]*p_len j = -1 for i in range(1, p_len): while j > -1 and pattern[j+1] != pattern[i]: j = pos[j] if pattern[j+1] == pattern
多模字符串匹配算法原理及Java实现代码

多模字符串匹配算法在这里指的是在一个字符串中寻找多个模式字符字串的问题.一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的.该算法广泛应用于关键字过滤.入侵检测.病毒检测.分词等等问题中.多模问题一般有Trie树,AC算法,WM算法等等. 背景在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下 for (String document : d
Python实现字符串匹配算法代码示例

字符串匹配存在的问题 Python中在一个长字符串中查找子串是否存在可以用两种方法:一是str的find()函数,find()函数只返回子串匹配到的起始位置,若没有,则返回-1:二是re模块的findall函数,可以返回所有匹配到的子串. 但是如果用findall函数时需要注意字符串中存在的特殊字符蛮力法字符串匹配: 将模式对准文本的前m(模式长度)个字符,然后从左到右匹配每一对对应的字符,直到全部匹配或遇到一个不匹配的字符.后一种情况下,模式向右移一位. 代码如下: def string_m
PowerShell中查找字符串位置的IndexOf函数使用实例

本文介绍在PowerShell中使用字符串的IndexOf函数,来查询一个字符串中是否存在另一个字符串,如果存在那么它在什么位置. IndexOf函数是String对象的静态方法,用于查找一个字符串在另一个字符串中的位置.如果查寻字符串在被查询字符串中不存在,则返回值为-1.如果存在,则返回查寻字符串所处的位置,位置是从0开始的. 下面看看例子: 在"123"中不存在"13" 复制代码代码如下: PS C:\Users\spaybow> "123&
浅谈JAVA字符串匹配算法indexOf函数的实现方法

前言相信每个学习过Java的人都使用过indexOf函数,indexOf函数我们可以查找一个字符串(模式串)是否在另一个字符串(主串)出现过,返回结果表示出现位置的下标,如果返回-1,表示模式串在主串中不存在,那么,你可曾想过这些查找函数又是如何实现的呢? 从indexOf源码看起首先我们先来看一下indexOf的源码,indexOf的使用方式比较多,这是我们以一个形参的为例. static String mainString = "Hello my name is HuangLinqing
浅谈java 字符串,字符数组,list间的转化

1.关于java.lang.string.split xxx.split()方法可以将一个字符串分割为子字符串,然后将结果作为字符串数组返回. 2.字符串转字符数组 String str =" aa.png,a2.png,a3.png"; String[] arrayStr =new String[]{}; arrayStr = str.split(","); 3.字符数组转list List list = java.util.Arrays.asList(array
浅谈Java 继承接口同名函数问题

在Java中如果一个类同时继承接口A与B,并且这两个接口中具有同名方法,会怎么样? 动手做实验: interface A{ void fun(); } interface B{ void fun(); } interface C extends A,B{ } public class Test implements C{ @Override public void fun() { System.out.println("hehe"); } public static void main
浅谈Java中hashCode的正确求值方法

本文研究的主要是Java中hashCode的正确求值方法的相关内容,具体如下. 散列表有一项优化,可以将对象的散列码(hashCode)缓存起来,如果散列码不匹配,就不会检查对象的等同性而直接认为成不同的对象.如果散列码(hashCode)相等,才会检测对象是否相等(equals). 如果对象具有相同的散列码(hashCode),他们会被映射到同一个散列桶中.如果散列表中所有对象的散列码(hashCode)都一样,那么该散列表就会退化为链表(linked list),从而大大降低其查询效率. 一
浅谈java 执行jar包中的main方法

浅谈java 执行jar包中的main方法通过 OneJar 或 Maven 打包后 jar 文件,用命令: java -jar ****.jar 执行后总是运行指定的主方法,如果 jar 中有多个 main 方法,那么如何运行指定的 main 方法呢? 用下面的命令试试看: java -classpath ****.jar ****.****.className [args] "****.****"表示"包名": "className"表示&
浅谈java字符串比较到底应该用==还是equals

当用new String("aaaa")对字符串做定义时,==会返回false,equals可以返回正常结果. 比如 System.out.println("a" == "a"); //true System.out.println("a".equals("a")); //true System.out.println("a".equals(new String("a"
浅谈java String.split丢失结尾空字符串的问题

java中的split函数用于将字符串分割为字符数组是很方便的,但由于不是很熟悉,犯了错误如下: String strtest = "1,2,"; String arry[] = strtest.split(","); 这样得到的数组元素个数只是2两个,为什么呢,最后一个","后没有内容,它没有作为空字符串成为第三个数组元素,结尾的空字符串被丢弃了! 这个函数还有另一种重载方式 :public String [] split (String
浅谈java中字符串数组、字符串、整形之间的转换

字符串数组转字符串(只能通过for循环): String[] str = {"abc", "bcd", "def"}; StringBuffer sB = new StringBuffer(); for (int i = 0; i < str.length;i++) { sB.append(str[i]); } String s = sB.toString(); 字符数组转字符串可以通过下面的方式: char[] data = {"
浅谈Java操作符与其优先级

几乎所有运算符都只能操作"主类型"(Primitives).例外是"="."= ="和"! =",它们能操作所有对象.除此以外,String类支持"+"和"+=". 基本类型存储了实际的数值.而并非指向一个对象的引用.所以在为其赋值的时候,是直接把一个地方的内容复制到了另一个地方.例如,对基本数据类型使用a=b,那么b的内容就复制给了a.若接着修改了a,而b根本不会受这种修改的影响.(在
浅谈java+内存分配及变量存储位置的区别

Java内存分配与管理是Java的核心技术之一,之前我们曾介绍过Java的内存管理与内存泄露以及Java垃圾回收方面的知识,今天我们再次深入Java核心,详细介绍一下Java在内存分配方面的知识.一般Java在内存分配时会涉及到以下区域: ◆寄存器:我们在程序中无法控制 ◆栈:存放基本类型的数据和对象的引用,但对象本身不存放在栈中,而是存放在堆中(new 出来的对象) ◆堆:存放用new产生的数据 ◆静态域:存放在对象中用static定义的静态成员 ◆常量池:存放常量 ◆非RAM存储:硬盘等永久

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

相关推荐

随机推荐