最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

淺談JAVA字符串匹配算法indexOf函數(shù)的實(shí)現(xiàn)方法

 更新時(shí)間:2020年07月14日 15:57:52   作者:黃林晴  
這篇文章主要介紹了淺談字符串匹配算法indexOf函數(shù)的實(shí)現(xiàn)方法,indexOf函數(shù)我們可以查找一個(gè)字符串(模式串)是否在另一個(gè)字符串(主串)出現(xiàn)過。對(duì)此感興趣的可以來了解一下

前言

相信每個(gè)學(xué)習(xí)過Java的人都使用過indexOf函數(shù),indexOf函數(shù)我們可以查找一個(gè)字符串(模式串)是否在另一個(gè)字符串(主串)出現(xiàn)過,返回結(jié)果表示出現(xiàn)位置的下標(biāo),如果返回-1,表示模式串在主串中不存在,那么,你可曾想過這些查找函數(shù)又是如何實(shí)現(xiàn)的呢?

從indexOf源碼看起

首先我們先來看一下indexOf的源碼,indexOf的使用方式比較多,這是我們以一個(gè)形參的為例。

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) + "");
}

運(yùn)行上面代碼的結(jié)果,返回的結(jié)果是17,說明模式串在主串中存在,并且第一次出現(xiàn)的位置下標(biāo)是17

indexOf方法最終會(huì)走到下面方法中,源碼如下所示:

/**
 * 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;
}

代碼行數(shù)不多,接下來我們來分析一下,上面的代碼,fromIndex默認(rèn)是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,因?yàn)槲覀円谥鞔胁檎夷J酱詓ourceZize > targetSize,所以從主串下標(biāo)為0開始,連續(xù)查找targetSize個(gè)字符,再從下標(biāo)為1開始后,一直到,下標(biāo)為sourceSize - targetSize ,舉個(gè)簡單的例子在ABCDEFG中查找EF:

上圖依次表示從i為0,到i為4時(shí)的依次比較,從圖中我們也可以看出,BF算法是比較耗時(shí)的,因?yàn)楸容^的次數(shù)較多,但是實(shí)際比較的時(shí)候主串和模式串都不會(huì)太長,所以這種比較的方法更容易使用。

現(xiàn)在我們回過頭看看indexOf的下半部分源碼,我相信其實(shí)不用解釋了。

RK算法

RK算法其實(shí)就是對(duì)BF算法的升級(jí),還是以上面的圖為例,在ABCDEFG中查找EF的時(shí)候,比如下標(biāo)為0的時(shí)候,我們?nèi)ケ容^A和E的值,不相等就不繼續(xù)往下比較了,但是比如我們現(xiàn)在查找CDF是否在主串中存在,我們要從C已知比較大E發(fā)現(xiàn)第三位不相等,這樣當(dāng)模式串前一部分等于主串,只有最后一位不相等的時(shí)候,比較的次數(shù)太多了,效率比較低,所以我們可以采用哈希計(jì)算來比較,哈希計(jì)算 后面我會(huì)補(bǔ)充一篇。

我們要將模式串和sourceSize - targetSize + 1 個(gè)字符串相比,我們可以先將sourceSize - targetSize + 1個(gè)模式串進(jìn)行哈希計(jì)算。與哈希計(jì)算后的模式串相比較,如果相等則存在,對(duì)于哈希沖突在一般實(shí)現(xiàn)中概率比較低,不放心的話我們可以在哈希值相等時(shí)候再比較一次原字符串確保準(zhǔn)確,哈希的沖突概率也和哈希算法的本身設(shè)計(jì)有關(guān)。這樣的話,我們首先計(jì)算AB的哈希值 與 模式串的相比較,然后計(jì)算BC的哈希值與模式串相比較,直到比較出相等的返回下標(biāo)即可。

到此這篇關(guān)于淺談字符串匹配算法從indexOf函數(shù)的實(shí)現(xiàn)方法的文章就介紹到這了,更多相關(guān)字符串匹配算法從indexOf函數(shù)的實(shí)現(xiàn)方法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Java調(diào)用Windows的DOS命令的方法

    Java調(diào)用Windows的DOS命令的方法

    這篇文章主要介紹了Java調(diào)用Windows的DOS命令的方法,其主要內(nèi)容思路是實(shí)現(xiàn)調(diào)用Windows的ipconfig命令,然后將輸出的信息通過IO流輸出到控制臺(tái)。有需要的小伙伴參考下
    2015-02-02
  • Java之mybatis使用limit實(shí)現(xiàn)分頁案例講解

    Java之mybatis使用limit實(shí)現(xiàn)分頁案例講解

    這篇文章主要介紹了Java之mybatis使用limit實(shí)現(xiàn)分頁案例講解,本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • springboot中nacos-client獲取配置的實(shí)現(xiàn)方法

    springboot中nacos-client獲取配置的實(shí)現(xiàn)方法

    本文主要介紹了springboot中nacos-client獲取配置的實(shí)現(xiàn)方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-04-04
  • SpringBoot教程_創(chuàng)建第一個(gè)SpringBoot項(xiàng)目

    SpringBoot教程_創(chuàng)建第一個(gè)SpringBoot項(xiàng)目

    這篇文章主要介紹了SpringBoot教程_創(chuàng)建第一個(gè)SpringBoot項(xiàng)目,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-06-06
  • SpringBoot2.1.4中的錯(cuò)誤處理機(jī)制

    SpringBoot2.1.4中的錯(cuò)誤處理機(jī)制

    這篇文章主要介紹了SpringBoot2.1.4中的錯(cuò)誤處理機(jī)制,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-10-10
  • java hasNextInt判斷是否為數(shù)字的方法

    java hasNextInt判斷是否為數(shù)字的方法

    今天小編就為大家分享一篇java hasNextInt判斷是否為數(shù)字的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2018-07-07
  • springcloud集成zookeeper的方法示例

    springcloud集成zookeeper的方法示例

    這篇文章主要介紹了springcloud集成zookeeper的方法示例,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2018-04-04
  • Java出現(xiàn)中文亂碼問題分析及解決方案

    Java出現(xiàn)中文亂碼問題分析及解決方案

    在Java開發(fā)中,處理中文亂碼是一個(gè)常見的問題,由于字符集和編碼的復(fù)雜性,開發(fā)者可能面臨各種導(dǎo)致亂碼的情況,正確地處理中文字符集對(duì)于確保應(yīng)用程序的可靠性和國際化至關(guān)重要,本文給大家介紹了Java中文亂碼分析及解決方案,需要的朋友可以參考下
    2024-02-02
  • Java設(shè)置Excel數(shù)據(jù)驗(yàn)證的示例代碼

    Java設(shè)置Excel數(shù)據(jù)驗(yàn)證的示例代碼

    數(shù)據(jù)驗(yàn)證是Excel 2013版本中,數(shù)據(jù)功能組下面的一個(gè)功能。本文將通過Java程序代碼演示數(shù)據(jù)驗(yàn)證的設(shè)置方法及結(jié)果,感興趣的可以了解一下
    2022-05-05
  • 4位吸血鬼數(shù)字的java實(shí)現(xiàn)思路與實(shí)例講解

    4位吸血鬼數(shù)字的java實(shí)現(xiàn)思路與實(shí)例講解

    今天小編就為大家分享一篇關(guān)于4位吸血鬼數(shù)字的java實(shí)現(xiàn)思路與實(shí)例講解,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來看看吧
    2019-03-03

最新評(píng)論

宜良县| 宁波市| 阿拉善盟| 沙雅县| 福鼎市| 大理市| 昭苏县| 松溪县| 开鲁县| 宣武区| 准格尔旗| 灵宝市| 华蓥市| 弥渡县| 东山县| 昌江| 道真| 信宜市| 青神县| 卓资县| 方城县| 吉木乃县| 台中市| 临桂县| 博爱县| 枣强县| 卢龙县| 永登县| 阿巴嘎旗| 开原市| 宽甸| 当涂县| 马边| 雅安市| 阿瓦提县| 诸城市| 繁昌县| 禹城市| 宁阳县| 封开县| 绥化市|