优于KMP算法的 BM改进算法——SUNDAY算法

/*优于KMP算法的 BM改进算法——SUNDAY算法*/
例：
Hello, world. There is a word! No, it's two word.
word
H不等于w，patt移动。src[i+ patt_len]为o，next[‘o’]为4，移动四步到’o’。o不等于w，patt再移动4为o。o不等于w，再次移动到There前面的空格那，src[i + patt_len]为’r’,next[‘r’]为2,移动两步到’h’，再移动->’ ’->’a’，next[‘r’]为2。patt移动w，之后的o、r、d都匹配了。

#include <stdio.h>
#include <string.h>

void SUNDAY(char*src, char *patt)
{
    size_t patt_len = strlen(patt),src_len = strlen(src);
    size_t next[256], i, m, match_len,succ = 0;
    char*match_str;

    for(i=0;i<256; i++) //初始化next数组
    {
        next[i] = patt_len + 1;
    }
    for(i=0;i<patt_len; i++) //匹配到patternstring中的某个字符需要往后移动的步数
    {
        next[patt[i]] = patt_len - i;
    }

    m = src_len - patt_len + 1;
    for(i=0;i<m; i += next[src[i + patt_len]]) //根据src[i+ patt_len]这个字符判断移动的步数
    {
        if(src[i]== *patt)
        {
            match_str = src + i + 1;
            match_len = 1;
            do
            {
                if(match_len== patt_len)
                {
                    printf("Match at %dn", i);
                    succ = 1;
                    break;
                }
            }
            while(*match_str++== patt[match_len++]);
        }
    }
    if(!succ)
    {
        printf("Hasnot matchn");
    }
}

int main()
{
    charsrc[100] = "Hello, world. There is a word! No, it's two word.";
    charpatt[10] = "word";
    SUNDAY(src, patt);
    return0;
}

2011-05-12 20:24 发表于百度空间，今搬至CU。