indexOf底層使用的方法是典型的BF算法。

1、KMP算法

由來

外國人： Knuth，Morris和Pratt發明了這個算法，然后取它三個的首字母進行了命名。所以叫做KMP。

KMP真的很難理解，建議多看幾遍 B站代碼隨想錄，文章也的再好

用處

時間復雜度O(n)

主要應用在 字符串匹配中

最長公共前后綴

將字符串拆分成以首字符開始的各個子串，然后依次判斷，下標 n與下標 length - n - 1的元素是否相等，若有 m個連續相等的字符，則最長公共前綴為 m

例如字符串：AABAAF的公共前后綴長度如下圖所示，紅色代表不相同，藍色代表元素相同

知道了公共前綴， 相應的可以利用我們獲取到的公共前綴表來找到當字符不匹配的時候指針應該移動的位置，如下圖所示：

下圖來自于 代碼隨想錄

核心：next數組

next數組就是用來存儲公共前綴的個數的， 例如上面的例子，他的next數組結果就應該是

int[] next = {0,1,0,1,2,0} 復制代碼

思路分析

• 前置條件， 字符串 s，前綴數組 int[] next
• 設置一個整數 j代表最長公共前后綴的個數
• 首先是初始化，我們的 next數組第一個元素肯定是 0
• 然后去 for循環我們的字符串，這里需要注意的是我們的for循環是從下標 1開始的
• 判斷 j必須大于 0不然的話在回溯過程中會發生 越界的情況，還要判斷元素是否相等

• • 若不相等則 j回溯到上一個 next數組下標
  • 這里需要注意的是要用 while循環，因為可能會一直進行回溯操作

• 當 s.charAt(j) == s.charAt(i)時，代表最長前后綴元素個數 +1，所以 j++
• 最后將 j的值賦給數組 next[i]

代碼展示

public static int KMP(String s, String p) {int slen = s.length();int plen = p.length();char[] str = s.toCharArray();char[] ptr = p.toCharArray();int[] next = new int[plen];cal_next(ptr, next);int k = -1;for (int i = 0; i < slen; i++) {while (k > -1 && ptr[k + 1] != str[i]) //ptr和str不匹配，且k>-1（表示ptr和str有部分匹配）k = next[k]; //往前回溯if (ptr[k + 1] == str[i])k ++;if (k == plen - 1) { //說明k移動到ptr的最末端return i - plen + 1; //返回相應的位置}}return -1; }public static void cal_next(char[] str, int[] next) {int len = str.length;next[0] = -1; //next[0]初始化為-1，-1表示不存在相同的最大前綴和最大后綴int k = -1; //k初始化為-1//如果下一個不同，那么k就變成next[k]，注意next[k]for (int q = 1; q <= len - 1; q++) {while (k > -1 && str[k + 1] != str[q]) { //是小于k的，無論k取任何值。k = next[k]; //往前回溯}if (str[k + 1] == str[q]) { //如果相同，k++k ++;}next[q] = k; //這個是把算的k的值（就是相同的最大前綴和最大后綴長）賦給next[q] }public static void main(String[] args) {long start = System.currentTimeMillis();String full = "BBC ABCDAB ABCDABCDABDE";String par = "ABCDABD";int res = KMP(full,par);//int res = full.indexOf(par);System.out.println(res+","+(System.currentTimeMillis() - start)+"ms"); }

2、BF與RK算法

2.1 BF算法

BF算法就是Brute Force，暴力匹配算法，也成為樸素匹配算法，主串的大小是sourceSize，模式串的大小是targetSize，因為我們要在主串中查找模式串，所以sourceZize > targetSize,所以從主串下標為0開始，連續查找targetSize個字符，再從下標為1開始后，一直到，下標為sourceSize - targetSize ,舉個簡單的例子在ABCDEFG中查找EF：

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

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

2.2 RK算法

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

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

3、String.index源碼

使用的測試代碼如下所示

String haystack = "mississippi", needle = "issip"; int i1 = haystack.indexOf(needle);對應的源碼方法重載跳轉如下所示：

• 先進入 indexOf（String str）方法
• 跳轉進入 indexOf(String str, int fromIndex)

• • 這個時候 fromIndex == 0

• 跳轉進入 inexOf(char[] source, int sourceOffset, int sourceCount, ? ? ? ? ? ?char[] target, int targetOffset, int targetCount, ? ? ? ? ? ?int fromIndex)

• • value表示 haystack元素的 char數組
  • value.length表示 haystack的長度
  • str.value表示 needle元素的 char數組
  • str.value.length表示 needle的長度

• 接下來我們看 indexOf方法的具體實現

String.indexOf()方法詳解

因為我沒有下載 java8源碼，所以直接在這里進行注釋標注了

// source: 當前字符串元素 // sourceOffset: 偏移量 // sourceCount： 當前字符串長度 // target： 目標字符串 // targetOffset：目標字符串偏移量 // targetCount： 目標字符串長度 // fromIndex： 索引位置 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;}// 如果目標字符串的長度為 0則直接返回 索引位置 （我們這里因為之前方法重載 fromIndex為 0 所以返回 0）if (targetCount == 0) {return fromIndex;}// 獲取目標 首字符char first = target[targetOffset];// 我們這里就是 源字符串長度 - 目標字符串長度， sourceOffset == 0int max = sourceOffset + (sourceCount - targetCount);// 循環，i == 0// 加入循環到了 max的索引位置還沒有找到和 目標字符串首字符相等的元素，則源字符串中肯定不包含目標字符串for (int i = sourceOffset + fromIndex; i <= max; i++) {// 搜索首字符所在位置if (source[i] != first) {while (++i <= max && source[i] != first);}// 找到了首字符，判斷其余字符位置是否相等if (i <= max) {int j = i + 1;// 根據目標字符串的長度截取源字符串從下標 i開始相同長度的字符串int end = j + targetCount - 1;// 遍歷判斷for (int k = targetOffset + 1; j < end && source[j]== target[k]; j++, k++);// 如果到最后一個元素都相同，則代表源字符串內包含目標字符串if (j == end) {// 這里就直接返回了 i 因為源字符串偏移量為 0return i - sourceOffset;}}}return -1; }

時間復雜度O(n*m)

4、為什么Java String.indexOf?()沒有使用更加“高效”的字符串搜索算法

為什么Java String indexOf 沒有使用更加“高效”的算法

參考：

java - Why does String.indexOf() not use KMP? - Stack Overflow

???????原來JDK的編寫者們認為大多數情況下，字符串都不長，使用原始實現可能代價更低。

? ? ? ?因為KMP和Boyer-Moore算法都需要預先計算處理來獲得輔助數組，需要一定的時間和空間，這可能在短字符串查找中相比較原始實現耗費更大的代價。在短字符串測試過程中，使用indexOf方法時要比KMP算法要快一點。KMP算法對與超長字符串子匹配速度上是優于IndexOf的。

? ? ? 因為KMP算法需要預先計算處理來獲得輔助數組，需要一定的時間和空間，這可能在短字符串查找中相比較原始實現耗費更大的代價。

? ? ? 而且一般大字符串查找時，程序員們也會使用其它特定的數據結構，查找起來更簡單。這有點類似于排除特定情況下的快速排序了。不同環境選擇不同算法。

5、總結起來有兩點：

• ① 高效的算法BM和KMP都是需要空間作為代價的，特別是BM，任何一個字符串都需要至少64K內存，考慮到L1 Cache大小，cost更不可知。
• ② JDK應該默認了不會使用Java String.indexOf查找過大的字符串，對于輕量級（通常不超過幾十個字符），及時暴力用時也非常短。這也提示，Java String.indexOf的客戶端程序員應該對于自己使用的API有所了解，如果要進行過大的字符串查找，應該自己設計算法（取出兩個字符串的value[]，然后實現BM或KMP）或調用第三方工具專門處理。

6、參考

java - Why does String.indexOf() not use KMP? - Stack Overflow

efficiency - Why does Java's String class not implement a more efficient indexOf()? - Software Engineering Stack Exchange

從 KMP算法到 Java的 String.indexOf(String str)方法-阿里云開發者社區

字符串匹配算法從indexOf函數講起 - 騰訊云開發者社區-騰訊云

字符串匹配算法總結 (分析及Java實現)_數據中國的博客-CSDN博客

KMP算法——字符串快速匹配_AAMahone的博客-CSDN博客?

總結

以上是生活随笔為你收集整理的为什么JDK中String类的indexof不使用KMP或者Boyer-Moore等时间复杂度低的算法编辑器的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。