sunday算法简单解析

落日映苍穹つ 2022-05-17 00:21 211阅读 0赞

## sunday算法解析 ##

\#\#\#\#\# Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：

> 只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。  
> 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1；  
> 否则，其移动位数 = 模式串中最右端的该字符到末尾的距离+1。  
> 下面举个例子说明下Sunday算法。假定现在要在文本串”substring searching algorithm”中查找模式串”search”。

1. 刚开始时，把模式串与文本串左边对齐：

substring searching algorithm
    search
    ^

2. 结果发现在第2个字符处发现不匹配，不匹配时关注文本串中参加匹配的最末位字符的下一位字符，即标粗的字符 i，因为模式串search中并不存在i，所以模式串直接跳过一大片，向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7，从 i 之后的那个字符（即字符n）开始下一步的匹配，如下图：

substring searching algorithm
    　　　 search
    　　　　^

3. 结果第一个字符就不匹配，再看文本串中参加匹配的最末位字符的下一位字符，是'r'，它出现在模式串中的倒数第3位，于是把模式串向右移动3位（r 到模式串末尾的距离 + 1 = 2 + 1 =3），使两个'r'对齐，如下：

substring searching algorithm
    　　　　  search
    　　　　　　　^

4. 匹配成功。
    
    回顾整个过程，我们只移动了两次模式串就找到了匹配位置，缘于Sunday算法每一步的移动量都比较大，效率很高。完。

public class Sunday { 
    
        public static void main(String[] args) {
    
            String desc = "the google searching the kmp";
    
            String pattern = "search";
    
            sunday(desc,pattern);
    
        }
    
        /** * 只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1； 否则，其移动位数 = 模式串中最右端的该字符到末尾的距离+1。 * @param desc * @param pattern * @return */
    
        public static void sunday(String desc,String pattern){
            char[] descChar = desc.toCharArray();
            char[] patternChar = pattern.toCharArray();
            int i=0,j=0,los=0;
            while (i <= (desc.length() - pattern.length() + j ) ){
                if (descChar[i] != patternChar[j]){
                    if (i <= (desc.length() - pattern.length() + j ) ){
                        //i是追随j的，所以使用逻辑当前判断
                        break;
                    }
    
                    los = cont(patternChar,descChar[i+patternChar.length-j]);
                    //如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1；
                    // 否则，其移动位数 = 模式串中最右端的该字符到末尾的距离+1。
                    if (los == -1){
                        //i-j回退，然后跳转长度为匹配串长度+1
                        i = i-j+patternChar.length+1;
                        j = 0;
                    }else {
                        //i-j回退i位置，patternChar.length-los-1取得当前跳转长度,+1
                        i = i-j+patternChar.length-los+1-1;
                        j = 0;
                    }
    
                }else {
                        //判断是否退出
                    if (j == (pattern.length() - 1)) {
                        System.out.println("the start pos is " + (i - j) + " the end pos is " + i);
                        i = i - j + 1;
                        j = 0;
                    } else {
                        i++;
                        j++;
                    }
                }
            }
    
        }
    
        /** * 判断当前字符在最后匹配串中最后出现的位置 * @param patternChar * @param p * @return */
        public static int cont(char[] patternChar,char p){
            for (int j = patternChar.length-1; j >=0; j--) {
                if (p == patternChar[j])
                    return j;
            }
            return -1;
        }
    
    }