Sunday算法的java实现

• Sunnday算法简介

• 一个示例

• java实现

Sunday算法简介

Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。 —— [ 百度百科 ]

相比于另外几个著名的字符串匹配算法，KMP以及BM算法而言，Sunday算法不仅理解起来比较容易，而且往往能有更好的速度。上面的描述可能太过于抽象，下面介绍一个简单的例子，来理解一下Sunday算法的基本思想。

一个示例

考虑被匹配字符串abcdebcdb，匹配字符串bcde

这里记被匹配字符串的位置为i，匹配字符串的位置为j

第一步，将两个字符串首对齐：

abcdebcdb
bcde

发现a与b不匹配，随后考虑i+匹配字符串长度的位置上的字符串是否在匹配字符

串中，若不在，则直接将匹配字符串的头对齐到该位置下一个的位置。这里发现

e在匹配字符串bcde中，随后将bcde中的e对齐到该位置（如有多个，优先对齐

后面的），变为

abcdebcdb
. bcde

找到一个匹配的，若要继续找下一个匹配的，将i的位置设置为匹配到的字符串

首的位置＋1即可。下面上代码：

JAVA实现

输入为空的情况在这里没有被添加，如有需要，可以自行添加，这个例子给出了
所有的被匹配到的字符串

public class Sunday {

    public void Sunday(String dest , String pattern){

        char[] destchars = dest.toCharArray();
        char[] patternchars = pattern.toCharArray();

        int i = 0;
        int j = 0;

        while(i <= (dest.length() - pattern.length() + j )  ){
            if( destchars[i] != patternchars[j] ){
                if(i == (dest.length() - pattern.length() + j )){
                    break;
                }
                int pos = contains(patternchars,destchars[i+pattern.length()-j]);
                if( pos== -1){
                    i = i + pattern.length() + 1 - j;
                    j = 0 ;
                }else{
                    i = i + pattern.length() - pos - j;
                    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++;
                }
            }
        }
    }

    private int contains(char[] chars,char target){
        for(int i = chars.length-1 ; i >= 0; i--){
            if(chars[i] == target){
                return i ;
            }
        }
        return -1;
    }

    public static void main(String[] args){
        Sunday sunday = new Sunday();
        sunday.Sunday("abcdebcdbcdebcde","bcde");
    }
}