indexOf原理，Java，javascript，python實現

 

簡介

　　最近做項目的時候，發現無論是前端還是後端，indexOf出現的概率都非常頻繁，今天我們來看下他的實現原理吧！

　　indexOf的含義：給定一個字元串去匹配另一個字元串的下標，如果匹配到，返回下標，如果匹配不到則返回-1，其實原理還是比較簡單的，如果需要你實現，那麼應該怎麼做呢？

 

原理

　　現在給定匹配的字元串A，原始字元串B，比如匹配字元串A等於「叫練」，原始字元串B等於「邊叫邊練，我喜歡叫練」，你可能一眼就發現「叫練」是最後兩個字元，我們以B做循環，一個一個單詞去匹配，先找「叫」，找到計數器加1，然後繼續找「練」，發現下個字元不是「練」，計數器清零，重新從「叫」開始查找，現在查找到B的倒數第二個字元了，下個字元是「練」計算器再加1，此時計數器等於2也正好是A字元串的長度，說明找到了，查找原理就是這樣一個過程；下面我們分別以Java，javascript，python方式實現下。

　　注意：下面程式碼沒有校驗，僅供參考，python是index方法，實現原理一樣，但找不到會報錯！

 

實現

Java實現

public static void main(String[] args) {
        String orgin = "邊叫邊練，我喜歡叫練";
        String serach = "叫練";
        int index = indexOf(orgin,serach);
        System.out.println(index);
    }

/**
     *  indexOf 演算法原理
     * @param orgin 原始字元串 B = 「邊叫邊練，我喜歡叫練」;
     * @param serachString 匹配字元串 A=「叫練」
     * @return int 下標
     */
public static int indexOf(String orgin,String serachString) {
    char[] chars = orgin.toCharArray();
    char[] sChars = serachString.toCharArray();
    //返回字元串下標
    int index = -1;
    //匹配字元串計數器，用於查詢是否匹配到完整字元串
    int s_index = 0;
    //全局計數器，用於計算下標
    int move = 0;
    for (int i=0; i<chars.length; i++) {
        move++;
        //如果匹配到「叫」,繼續向下開始匹配「練」
        if (chars[i] == sChars[s_index]) {
            s_index++;
            if(s_index == sChars.length) {
                index = move-sChars.length;
                break;
            }
        } else {
            s_index = 0;
        }
    }
    return index;
}

 

Javascript實現​

 1 /**
 2      * @param orgin 原始字元串 B = 「邊叫邊練，我喜歡叫練」;
 3      * @param serachString 匹配字元串 A=「叫練」
 4      **/
 5     function indexOf(orgin,serachString) {
 6         //返回字元串下標
 7         var index = -1;
 8         //匹配字元串計數器，用於查詢是否匹配到完整字元串
 9         var s_index = 0;
10         //全局計數器，用於計算下標
11         var move = 0;
12         for (var i=0; i<orgin.length; i++) {
13             move++;
14             //如果匹配到「叫」,繼續向下開始匹配「練」
15             if (orgin.substr(i,1) == serachString.substr(s_index,1)) {
16                 s_index++;
17                 if(s_index == serachString.length) {
18                     index = move-serachString.length;
19                     break;
20                 }
21             } else {
22                 s_index = 0;
23             }
24         }
25         return index;
26     }

 

python實現

 1 # indexOf 演算法原理
 2 # @param orgin 原始字元串 B = 「邊叫邊練，我喜歡叫練」;
 3 # @param serachString 匹配字元串 A=「叫練」
 4 # @return int 下標
 5 def index(orgin, serachString):
 6     # 返回字元串下標
 7     index = -1
 8     # 匹配字元串計數器，用於查詢是否匹配到完整字元串
 9     s_index = 0
10     # 全局計數器，用於計算下標
11     move = 0
12     for letter in enumerate(orgin):
13         move = move + 1
14         # 如果匹配到「叫」,繼續向下開始匹配「練」
15         if letter[1] == serachString[s_index]:
16             s_index = s_index + 1
17             if s_index == len(serachString):
18                 index = move - len(serachString)
19                 break
20         else:
21             s_index = 0;
22 
23     return index

 

Tags:

VirMach 便宜 VPS