转载

字符串匹配之Sunday算法

Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配算法. 其核心是在匹配失败时关注文本主串中参加匹配的最末位字符的下一位字符. 如果该字符没有在匹配串中出现则直接跳过，即移动步长= 匹配串长度+1；否则，同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1.

由于Sunday算法相对于KMP来说实在是太好理解了, 所以直接分两部分给出代码:

移动步长的求法
Sunday算法实现

移动步长的求法

int *getNext(string const p)
{
    int length = (int)p.size();
    int *next = new int[length];
    for (int i = length-1; i >= 0; --i) {
        char chr = p[i];
        int j = length-1;
        //从后往前遍历是否存在相同的字符
        bool flag = false;
        while (j > i) {
            if (chr == p[j]) {
                flag = true;
                break;
            }
            --j;
        }
        //如果不存在, 则记录其到末尾的距离, 否则记录最右侧相同字符到末尾的距离
        next[i] = flag?(next[j]):(length - i - 1);
    }
    return next;
}

Sunday算法实现

int sunDay(string const t, string const p, int *next)
{
    int i = 0;
    int j = 0;
    int len_t = (int)t.length();
    int len_p = (int)p.length();
    while (i < len_t) {
        if (t[i] == p[j]) {
            ++i;
            ++j;
            if (j == len_p) {
                return i - len_p;
            }
        }else{
            //第i位失配, 主串中参加匹配的末位字符的下一位为(i-j+len_p)
            if (t.find(t[i-j+len_p]) == t.npos) {
                //如果未找到, 移动步长= 匹配串长度+1
                i = (i - j + len_p + 1);
                j = 0;
            }else{
                //如果找到了, 将模式串中最右侧的字符与其对齐
                int index = (int)p.find(t[i-j+len_p]);
                i = (i - j +  next[index] + 1);
                j = 0;
            }
        }

    }
    return NO_MATCH;
}

测试用例

int main(int argc, const char * argv[]) {

    string p = "aaab";
    string t = "aaaaaaaaaab";
    int *next = getNext(p);
    int result =  sunDay(t, p, next);
    cout << result << endl;
    delete[] next;


    string p1 = "abd";
    string t1 = "abcdabccccabd";
    int *next1 = getNext(p1);
    int result1 =  sunDay(t1, p1, next1);
    cout << result1 << endl;
    delete[] next1;

    return 0;
}

原文 http://www.devzhang.cn/2016/12/23/字符串匹配之Sunday算法/

正文到此结束