C / C++学习笔记：实现Sunday算法

Sunday算法

Sunday 算法于 1990 年 Daniel M.Sunday 提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday 算法的实现可比 KMP，BM 的实现容易太多，而且速度上也是快上两三倍。

核心思想

在匹配过程中，不需要模式字符串以确保从左到右或从右到左按比较以比较发现不匹配，算法可以跳过尽可能多的字符进行下一个匹配，从而提高了匹配效率。

具体原理操作如下：

假设

str1：abcceabcaabcd

str2：abcd

str1_len = str1.length();

str2_len = str2.length();

从头开始str1 与 str2 以此匹配，找不到C和d匹配。不匹配时则查看 str2字符串的后一位字符（即e），发现str2字符没有一个与之相同的，此时，需要跳过一大片的字符，即到达str2_len+1的后一个字符开始匹配(即a)

str1：abcceabcaadsdabcd

str2：-----abcd

从str1的a开始匹配，但在相对于a的第二个字符却与str2不匹配，所以又查看str2字符串的后一位字符现a字符与str2的第一个字符匹配，所以str2字符串需要偏移到跟str1字符串相匹配的位置，重复步骤，相对于第一个字符（a）的的第二个位置（即d）但与之不匹配，所以又查看str2字符串的后一位字符（即a）。

str1：abcceabcaadsdabcd

str2：-------------- abcd

发现a字符与str2的第一个字符匹配，所以str2字符串需要偏移到跟str1字符串相匹配的位置，但是现在在str1相对于第一个字符（a）的的第二，三，四的位置都与str2的z字符相匹配。所以匹配成功

str1：abcceabcaadsdabcd

str2：-------------------- abcd

若是觉得我解释的不清楚的话：这个是大神的博客，附有图片解释，或许会更好


int  test(const string str1, const string str2){

    int str1_len = str1.length();
    int str2_len = str2.length();

    int i = 0, j = 0;
    long int index = 0;  //下标

    while(index < str1_len - str2_len){

        //这个主要两个字符串的比较，比较是否全等。
        for (; i <str2_len ; ++i) {
            //表示全等的过程
            if(i == str2_len - 1){
                return index + 1;
            }

            //若是有一个不对等。。那么久没必要再循环了，直接退出
            if(str2[i] != str1[index + i]){
                break;
            }
        }


        //z这个主要是上面匹配不成功的话，我们就要把下标index偏移到str2的后面
        for (j = 0; j < str2_len; ++j) {
            if(str2[j] == str1[index + str2_len]){
                //这里设置偏移量
                index += str2_len -j;
                break;
            }

            if(j == str2_len -1){
                index += str2_len ;

            }

        }

    }

    cout << "没有匹配到包含的字符串" << endl;
}

运算结果

0a36abc3c661062c02ba740629f5d51.png

注意

这个字节写的代码是在102400个字节内能查询到，再多的话就会导致查询失败。以后我会继续完善的。

百度大佬的代码

//注意这里的数据大小可以更改，当时为了测试长文本给改成那么大、
#define MAX_CHAR 25600  
#define MAX_LENGTH 100000

void GetNext(string & p, int & m, int next[])
{
    for (int i = 0; i < MAX_CHAR; i++)
        next[i] = -1;
    for (int i = 0; i < m; i++)
        next[p[i]] = i;
}

void Sunday(string & s, int & n, string & p, int & m)
{
    int next[MAX_CHAR];
    GetNext(p, m, next);

    int j;  // s 的下标
    int k;  // p 的下标
    int i = 0;
    bool is_find = false;
    while (i <= n - m)
    {
        j = i;
        k = 0;
        while (j < n && k < m && s[j] == p[k])
            j++, k++;

        if (k == m)
        {
            cout << "在主串下标 " << i << " 处找到匹配\n";
            is_find = true;
        }

        if (i + m < n)
            i += (m - next[s[i + m]]);
        else
            break;
    }

    if (!is_find)
        cout << "未找到匹配\n";
}

大神的代码测试：

7c2064375e21d7e5d9de50922a5ef0a.png

注意

大神的代码速度都差不多，但是稳定性更强，更加的优化，这个是我值得借鉴的地方。

计算代码运行时间

#include <time.h>

int main()

{

                clock_t start,end;
                start=clock();

                函数体

                end=clock();
//C语言
                 printf("totile time=%f\n",(float)(end-start)*1000/CLOCKS_PER_SEC);
//CPP
                cout << "time: " << (float)(end-start)/CLOCKS_PER_SEC << "s" << endl;

总结

感觉在此次学习过程中，应用的也只是基础的C语言，CPP语言的知识
我可以改进的地方：

偏移量应该，写一个偏移量表来的
在查询字符串中是否包含单字符的中，，应该单独拿出二分查询法，提高查询效率。

3.等过后应该多看一下网上大神的代码，是如何实现的

最后

不知道不同人运行的不同编译器是否会出现错，若是遇到错误的地方，欢迎留言。若是你有更好的，更有效率的方法，也欢迎留言告知，大家一起进步，一起讨论、可以相互关注，相互学习