Sunday算法

匹配原理

从前往后匹配，如果遇到不匹配情况，则查看母串S中参与匹配的最后一位的下一位字符，记做C，如果C出现在模板串T中，选择模板串中C最右出现的位置对齐；如果C没有出现在模板串T中，直接跳过该匹配区域。

算法演示

母串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

匹配失败：
查找母串S参与匹配的最后一位字符的下一字符，基黄色的S；
在T中，字符’S’出现两次，按照原理，选择T中最右位置出现的’S’进行对齐，那么可以得到：

匹配失败.png

假设母串S为：S E A R C H S U B Z T R I N G
那么当匹配到上述情况时，字符’Z’在T中没有出现，那么就可以得到下面的情况：

匹配失败.png

可以看到，当匹配失败时，跳过的区域很大。

代码如下:

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

        int i=0; // S 下标
        int j =0;// T 下标
        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]; // 字符的种类数目
        //   默认S中的任何字符均不出现在T中，那么每次移动的距离为T的长度 + 1
        for(int i=0; i<moveLen.length; ++i){
            moveLen[i] = T.length() + 1;
        }

        //查找能够出现在T中的字符，若一个字符出现多次，选择最右位置的字符，所以T的下标遍历从0开始
        for(int i=0; i<T.length(); i++){
            moveLen[T.charAt(i)] = T.length() - i;
        }
    }