字符串匹配算法（一）

一、BF算法

      BF算法是普通的模式匹配算法，其基本思想就是将目标串的第一个字符与模式串的第一个字符进行匹配。若相等，则继续比较第二个字符；若不相等，则比较目标串的第二个字符和模式串的第一个字符。依次比较下去，直到得出最后的匹配结果。

      示例代码：

static int bf(const char *src, const char *des)
{
    int i, pos;
    int len_s, len_d;

    if(src == NULL || des == NULL)
        return -1;

    len_s = strlen(src);
    len_d = strlen(des);

    for(pos = 0; pos < len_s - len_d; pos++) {
        for(i = pos; i - pos < len_d; i++) {
            if(src[i] != des[i - pos])
                break;
        }

        if((i - pos) == len_d)
            return pos;
    }

    return -1;
}

二、Sunday算法

      Sunday算法是Daniel M.Sunday于1990年提出的一种比BM算法搜索速度更快的算法。其核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。Sunday算法思想跟BM算法很相似，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过，即移动步长= 匹配串长度+1；否则，同BM算法一样，即移动步长=匹配串中最右端的该字符到末尾的距离+1。

     例如我们要在"substring searching"查找"search"，刚开始时，把子串与文本左边对齐：

s

u

b

s

t

r

i

n

g

s

e

a

r

c

h

i

n

g

s

e

a

r

c

h

     结果在第二个字符处发现不匹配，于是要把子串往后移动。但是该移动多少呢？这就是各种算法各显神通的地方了，最简单的做法是移动一个字符位置；KMP是利用已经匹配部分的信息来移动；BM算法是做反向比较，并根据已经匹配的部分来确定移动量。这里要介绍的方法是看紧跟在当前子串之后的那个字符（上图中的'i')。

      显然，不管移动多少，这个字符是肯定要参加下一步的比较的，也就是说，如果下一步匹配到了，这个字符必须在子串内。所以，可以移动子串，使子串中的最右边的这个字符与它对齐。现在子串'search'中并不存在'i'，则说明可以直接跳过一大片，从'i'之后的那个字符开始作下一步的比较，如下图：

s

u

b

s

t

r

i

n

g

s

e

a

r

c

h

i

n

g

s

e

a

r

c

h

      比较的结果，第一个字符就不匹配，再看子串后面的那个字符是'r'，它在子串中出现在倒数第三位，于是把子串向前移动三位，使两个'r'对齐，如下：

s

u

b

s

t

r

i

n

g

s

e

a

r

c

h

i

n

g

s

e

a

r

c

h

     这次匹配成功了！回顾整个过程，我们只移动了两次子串就找到了匹配位置。可以证明：用这个算法，每一步的移动量都比BM算法要大，所以肯定比BM算法更快。

以上Sunday算法文字描述摘自 这里。

代码实现：

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


#define LETTER_MAX_LEN 256
#define MAXLINE 1024

static int sunday(const char *src, const char *des)
{
    int i, pos = 0;
    int len_s, len_d;
    int alphabet[LETTER_MAX_LEN] = {0};

    if(src == NULL || des == NULL)
        return -1;

    len_s = strlen(src);
    len_d = strlen(des);

    for(i = 0; i < LETTER_MAX_LEN; i++)
        alphabet[i] = len_d;

    for(i = 0; i < len_d; i++)
        alphabet[des[i]] = len_d - i - 1;

    for(pos = 1; pos <= len_s - len_d; ) {
        for(i = pos - 1; i - pos + 1 < len_d; i++) {
            if(src[i] != des[i - pos + 1])
                break;
        }

        if((i - pos + 1) == len_d)
            return pos;
        else
            pos += alphabet[src[pos + len_d - 1]] + 1;
    }

    return -1;
}

int main(int argc, char **argv)
{
    FILE *fp = NULL;
    char line[MAXLINE] = {0};
    int linesNum;

    fp = fopen(argv[1], "r");
    if(fp == NULL) {
        printf("can not open file %s\n", argv[1]);
        return -1;
    }

    while ((fgets(line, MAXLINE, fp)) != NULL) {
        linesNum++;
        if (sunday(line, "chinaunix") >= 0)
            printf("find match at line %d\n", linesNum);
    }

    fclose(fp);
    fp = NULL;

    return 0;
}