快捷導航

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

更新時間：2020年07月14日 15:57:52 作者：黃林晴

這篇文章主要介紹了淺談字符串匹配算法indexOf函數(shù)的實現(xiàn)方法，indexOf函數(shù)我們可以查找一個字符串（模式串）是否在另一個字符串（主串）出現(xiàn)過。對此感興趣的可以來了解一下

前言

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

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

運行上面代碼的結(jié)果，返回的結(jié)果是17，說明模式串在主串中存在，并且第一次出現(xiàn)的位置下標是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;
}

代碼行數(shù)不多，接下來我們來分析一下，上面的代碼，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開始，連續(xù)查找targetSize個字符，再從下標為1開始后，一直到，下標為sourceSize - targetSize ,舉個簡單的例子在ABCDEFG中查找EF：

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

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

RK算法

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

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

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

您可能感興趣的文章: