前言
相信每個(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è)形參的為例。
|
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) + "");} |
運(yùn)行上面代碼的結(jié)果，返回的結(jié)果是17，說明模式串在主串中存在，并且第一次出現(xiàn)的位置下標(biāo)是17
indexOf方法最終會(huì)走到下面方法中，源碼如下所示:
|
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;} |
代碼行數(shù)不多，接下來我們來分析一下，上面的代碼，fromIndex默認(rèn)是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，因?yàn)槲覀円谥鞔胁檎夷Ｊ酱詓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í)就是對BF算法的升級，還是以上面的圖為例，在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ì)算后的模式串相比較，如果相等則存在，對于哈希沖突在一般實(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)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/huangliniqng/article/details/103677768
