Sunday算法

匹配原理

從前往后匹配，如果遇到不匹配情況，則查看母串S中參與匹配的最后一位的下一位字符，記做C，如果C出現(xiàn)在模板串T中，選擇模板串中C最右出現(xiàn)的位置對齊；如果C沒有出現(xiàn)在模板串T中，直接跳過該匹配區(qū)域。

算法演示

母串S：? S E A R C H S U B S T R I N G
模板串T：S U B S T R I N G

開始匹配：

開始匹配.png

匹配成功，開始下一次匹配：

下一次匹配.png

匹配失?。?br> 查找母串S參與匹配的最后一位字符的下一字符，基黃色的S；
在T中，字符’S’出現(xiàn)兩次，按照原理，選擇T中最右位置出現(xiàn)的’S’進(jìn)行對齊，那么可以得到：

匹配失敗.png

假設(shè)母串S為：S E A R C H S U B Z T R I N G
那么當(dāng)匹配到上述情況時，字符’Z’在T中沒有出現(xiàn)，那么就可以得到下面的情況：

匹配失敗.png

可以看到，當(dāng)匹配失敗時，跳過的區(qū)域很大。

代碼如下:

/**
     *
     * @param S 母串
     * @param T 模式串
     * @return
     */
    static int sunday(String S, String T){
        int[] moveLen = getMoveLength(T);

        int i=0; // S 下標(biāo)
        int j =0;// T 下標(biāo)
        while (j<T.length() && i<S.length()){

            for(j=0; j<T.length() && i+j <S.length() && S.charAt(i+j)==T.charAt(j); ++j) ;

            // 匹配成功
            if(j == T.length()) return i;

            // S中沒有找到含T的字符串
            if(i+T.length() >= S.length()) return -1;

            //移動S的索引
            i += moveLen[S.charAt(i+T.length())];

        }
        return -1;

    }

    static int[] getMoveLength(String T){
        int[] moveLen = new int[256]; // 字符的種類數(shù)目
        //   默認(rèn)S中的任何字符均不出現(xiàn)在T中，那么每次移動的距離為T的長度 + 1
        for(int i=0; i<moveLen.length; ++i){
            moveLen[i] = T.length() + 1;
        }

        //查找能夠出現(xiàn)在T中的字符，若一個字符出現(xiàn)多次，選擇最右位置的字符，所以T的下標(biāo)遍歷從0開始
        for(int i=0; i<T.length(); i++){
            moveLen[T.charAt(i)] = T.length() - i;
        }
    }