Sunday算法

sunday算法是字符串模式匹配算法,是在BM算法上的优化,由 Daniel M.Sunday 在 1990年提出。

该字符串匹配算法由前往后进行

假设字符串为 HEREIBBSASIMPLEXEXAMPLE,搜索词为 EXAMPLE

HEREIBBSASIMPLEXEXAMPLE
EXAMPLE

从前往后,匹配失败,取最后一个字符 S,查找 EXAMPLE 里最后一次出现S的位置,没找到,移动全部

HEREIBBSASIMPLEXEXAMPLE5
        EXAMPLE

从前往后,匹配失败,取末尾后面的字符 X,查找 EXAMPLE 里最后一次出现X的位置,移动并对齐

HEREIBBSASIMPLEXEXAMPLE5
              EXAMPLE
HEREIBBSASIMPLEXEXAMPLE5
              EXAMPLE

从前往后,在第三个字符匹配失败,取末尾后面的字符 L,查找 EXAMPLE 里最后一次出现L的位置,移动并对齐 

HEREIBBSASIMPLEXEXAMPLE5
                EXAMPLE

从前往后匹配,匹配成功


linux c例子

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

void sunday_preprocess(char *pat, int n, int *bc)
{
    int i;

    for (i = 0; i < 256; i++)
        bc[i] = -1;

    for (i = 0; i < n; i++) {
        bc[pat[i]] = i;
    }
}

void sunday_search(char *pat, char *txt)
{
    int m,n,i,j,s;

    m = strlen(pat);
    n = strlen(txt);

    int bc[256];

    sunday_preprocess(pat, m, bc);

    s = 0;
    /*
      j 为 pat 索引
      s 为 txt 索引
    */
    while (s <= (n-m)) {

        //每次都从第一个字符开始匹配
        j = 0;
        while (j < m && pat[j] == txt[s+j])
            j++;

        if (j == m) {
            printf("found at index %d\n", s);
            s += m;
        } else {
            i = bc[txt[s+m]];
            if (i == -1)
                s += m + 1;
            else
                s += m - i;
        }

    }
}

int main(int argc, char **argv) 
{
    if (argc != 3)
        return 0;

    char *pat = argv[2];
    char *txt = argv[1];

    sunday_search(pat, txt);

    return 0;
}



上一篇: BM算法
下一篇: 有限自动机
作者邮箱: 203328517@qq.com