美文网首页
字符串匹配 - BF和RK算法

字符串匹配 - BF和RK算法

作者: 天命_风流 | 来源:发表于2020-03-28 15:22 被阅读0次

    字符串匹配有很多种算法,今天在这里先介绍两种比较简单的算法:BF 和 RK 算法。之后我们会学习其它更复杂的匹配算法。

    BF(Brute Force)算法

    BF算法中文叫做暴力匹配算法,也是最朴素的匹配算法。它的设计思想非常简单,易懂,当然相应的,它的性能并不高。

    主串 和 模式串:在进行算法介绍前,先定义这两个概念。例如:要在 A 中寻找 B ,那么 A 就是主串,B 就是模式串。

    对于 BF 算法来说,它的思想很容易概括:从头在主串中依次寻找模式串。举个例子你会很清楚:

    暴力匹配-BF算法.jpg

    性能分析

    时间复杂度:极端情况下,主串为 “aaa...aaa”,模式串是“aaaaab”。每次比对都要进行到最后一位才能确定是否匹配成功。假设主串有 n 个字符,模式串有 m 个字符,则要比对 n-m+1 次,所以,最坏情况为 O(n*m)。
    尽管复杂度很高,但是这种极端情况很难遇到,反而由于 BF 算法思想简单,易实现,易维护等,成为了非常常用的字符串匹配算法。

    RK算法

    RK算法的思路是这样的:对主串中的 n-m+1 个子串分别求哈希值,然后逐个与模式串的哈希值比较。如果相等,就说明匹配(暂时不考虑哈希冲突,后面会讲),如果不相等,就说明不匹配。由于哈希值是数字,所以哈希的比较非常快,效率也会提升: RK匹配.jpg

    但是在这里有一个问题:在计算子串的哈希值的时候,我们需要遍历子串中的每个字符,如果我们循规蹈矩地遍历字符,尽管比对效率提高了,但是构造哈希值的过程却非常耗时。这就导致算法的整体效率并不高。
    有什么方法可以提高计算哈希值的效率呢?

    高效的哈希值的计算方法

    首先,我们确定哈希值的计算方法,在这里,我们假设字符串只有 a~z 这 26 个小写字母,我们就用 二十六进制 来表示一个字符串。这样我们会有如下的计算方式:

    RK-哈希计算.jpg 随后,我们注意一下在子串中两个相邻子串的计算方式: RK-字符串哈希.jpg
    你会发现,它们之间的计算有如下规律: RK-哈希关系.jpg

    这样,我们就不必每次都计算子串的哈希值了,而是可以根据上一个子串计算得到。这样,我们减少了对内存的访问次数,同时与模式串的比较也非常高效。

    在这里还有一个小技巧,你可以将二十六进制每一位的值预先计算好,这样可以减轻计算机的计算负担: RK-哈希计算暂存.jpg

    用散列冲突减少计算负担

    按照上面的逻辑,字符串的散列值不会产生散列冲突。但是这也带来了一个问题,如果模式串的长度非常长,比如达到 100 位,那计算出来的数值就会非常大,所需要的散列表的空间也难以接受。
    这里,我们就需要改变哈希函数或者对哈希值进行取模了,而这样势必会产生散列冲突。这就需要我们对性能和应用场景进行综合考虑了。

    性能分析

    时间复杂度:程序分为两个部分:第一部分是根据主串构建子串的哈希值,这需要遍历字符串,时间复杂度为O(n)。第二部分是使用子串的哈希值和模式串进行比对,这里需要遍历 n-m+1 个子串的哈希值,所以,这一部分的时间复杂度也是O(n)。
    综上,RK算法的整体时间复杂度是O(n)。

    小结

    BF 算法是最简单、粗暴的字符串匹配算法,它拿模式串依次与主串中的子串进行匹配。时间复杂度较高。但是在实际的软件开发中,由于这种算法的实现简单,所以在处理小规模的字符串匹配的时候很好用。

    RK 算法是借助哈希算法对 BF 算法进行改造,即分别求子串的哈希值,然后利用哈希值进行比对,以减少比较时间。既然 RK 算法使用到了哈希算法,就要考虑哈希函数的设计问题和对散列冲突的处理。

    感悟

    之前我们提到过,用优势弥补不足,对计算机来说,优势是计算快速,不足是内存访问缓慢。学习了今天的匹配算法,尤其是了解了在 RK 算法中对哈希的应用,你对这句话是否有了更深的感悟?


    以上就是本节的全部内容

    注:本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结,我大量引用了其中的代码和截图,如果想要了解具体内容,可以前往极客时间

    一个代码实例

    我曾经写过一个通讯录软件,其中有一个查找信息的功能就使用到了字符串查找,当时不知道 BF 算法,但是使用的思想和 BF 完全一致,下面就将段代码放在下面,可以拿来参考。

    #include<stdio.h>
    #include<iostream>
    #pragma warning(disable:4996)
    using namespace std;
    
    
    typedef struct person           //设置基本结构
    {
        char name[20];
        char sex[10];
        char address[50];
        char number[15];
        struct person *next;
    }person,*zz;
    
    void create_for_head(zz &head);                 //声明需要的所有的函数
    void delete_person(zz want, zz q);
    void change_person(zz p);
    void add_person(zz &head);
    int search_person(char cx[20], zz who);
    void print_list(zz head);
    void print_person(zz temp);
    void search_list(zz head);
    void delete_list(zz head);
    void change_list(zz head);
    
    
    
    
    void create_for_head(zz &head)              //初始化这个通讯录
    {
        head =(zz)malloc(sizeof(person));       
        head->next = NULL;
    
        strcpy(head->name, "姓名");           //为这个通讯录事先存储一些信息
        strcpy(head->sex, "性别");
        strcpy(head->address, "地址");
        strcpy(head->number, "号码");
    
        zz p,q;
        p = head;
        q = (zz)malloc(sizeof(person));
        q->next = NULL;
        strcpy(q->name, "张三");
        strcpy(q->sex, "女");
        strcpy(q->address, "北京");
        strcpy(q->number, "12345678901");
        p->next = q;
        p = p->next;
    
        q = (zz)malloc(sizeof(person));
        q->next = NULL;
        strcpy(q->name, "李四");
        strcpy(q->sex, "男");
        strcpy(q->address, "辽宁");
        strcpy(q->number, "9876543210");
        p->next = q;
        p = p->next;
    
        q = (zz)malloc(sizeof(person));
        q->next = NULL;
        strcpy(q->name, "谭同学");
        strcpy(q->sex, "男");
        strcpy(q->address, "新疆");
        strcpy(q->number, "13384466772");
        p->next = q;
        p = p->next;
    
        q = (zz)malloc(sizeof(person));
        q->next = NULL;
        strcpy(q->name, "杨老师");
        strcpy(q->sex, "男");
        strcpy(q->address, "吉林");
        strcpy(q->number, "16875465198");
        p->next = q;
        p = p->next;
    
        q = (zz)malloc(sizeof(person));
        q->next = NULL;
        strcpy(q->name, "吕同学");
        strcpy(q->sex, "女");
        strcpy(q->address, "天津");
        strcpy(q->number, "79987413642");
        p->next = q;
        p = p->next;
    }
    
    void add_person(zz &head)           //为通讯录添加一个人员信息
    {
        zz p, q;
        q = head;
        for (; q->next != NULL;)
        {
            q = q->next;
        }
        p = (zz)malloc(sizeof(person));
        p->next = NULL;
        cout << "请输入人员的通讯信息:姓名、性别、地址、号码" << endl;
        cin >> p->name >> p->sex >> p->address >> p->number;
        q->next = p;
        system("cls");
        cout << "操作已完成" << endl;
    }
    
    void print_list(zz head)                //输出这个通讯录的信息
    {
        zz i;
        i = head;
        for (; i; i = i->next)
        {
            cout << i->name << "\t" << i->sex << "\t" << i->address << "\t" << i->number << endl;
        }
    }
    
    void print_person(zz temp)              //输出一个person的信息
    {
        if (temp!= NULL)
        {
            cout << temp->name << "\t" << temp->sex << "\t" << temp->address << "\t" << temp->number << endl;
        }
    }
    
    void search_list(zz head)               //执行查询操作
    {
        zz p,q;
        cout << "输入部分信息进行查找:" << endl;
        char search[20];
        cin >> search;
        p = head->next;
        q = head;
        int x = 0;
        while (p)
        {
            if (search_person(search, p))
            {
                if (x == 0)cout << "姓名" << "\t" << "性别" << "\t" << "地址" << "\t" << "号码" << "\t" << endl;
                print_person(p);
                x++;
            }
            q = q->next;
            p = p->next;
        }
        if (x == 0)
        {
            system("cls");
            cout << "没有查询到任何与之相关的信息" << endl<<endl;
        }
    }
    
    int search_person(char cx[20], zz who)      //用于查找一段信息是否属于某个person
    {
        int i, m, n;
        m = strlen(cx);             //查询号码
        n = strlen(who->number);
        int p = 0;
        for (i = 0; i <= n; i++)
        {
            if (cx[p] == who->number[i])
            {
                p++;
                if (p == m) return 1;
            }
            else p = 0;
        }
    
        n = strlen(who->name);          //查询姓名
        p = 0;
        for (i = 0; i <= n; i++)
        {
            if (cx[p] == who->name[i])
            {
                p++;
                if (p == m) return 1;
            }
            else p = 0;
        }
    
        n = strlen(who->address);       //查询地址
        p = 0;
        for (i = 0; i <= n; i++)
        {
            if (cx[p] == who->address[i])
            {
                p++;
                if (p == m) return 1;
            }
            else p = 0;
        }
    
        n = strlen(who->sex);       //性别
        p = 0;
        for (i = 0; i <= n; i++)
        {
            if (cx[p] == who->sex[i])
            {
                p++;
                if (p == m) return 1;
            }
            else p = 0;
        }
        return 0;
    }
    
    void delete_person(zz want,zz q)        //删除一个person
    {
        zz temp;
        temp = want;
        want = temp->next;
        q->next = temp->next;
        want = q->next;
        free(temp);
        cout << "已删除" << endl;
    }
    
    void delete_list(zz head)           //从通讯录中执行删除操作
    {
        zz p=head->next, q=head;
        char name[20];
        cout << "请输入要删除的人的姓名" << endl;
        cin >> name;
        int pd=1;
        while (p)
        {
            if (!strcmp(p->name, name))
            {
                delete_person(p, q);
                break;
            }
            q = q->next;
            p = p->next;
        }
        if (p == NULL)cout << "查找不到该人信息" << endl;
    }
    
    void change_person(zz p)            //修改一个person的信息
    {
        cout << "请输入这个人的新信息" << endl;
        cin >> p->name >> p->sex >> p->address >> p->number;
    }
    
    void change_list(zz head)       //从通讯录中执行修改操作
    {
        zz p = head;
        char name[20];
        cout << "你想要修改谁的信息?" << endl;
        cin >> name;
        while (p)
        {
            if (!strcmp(p->name, name))
            {
                change_person(p);
                cout << "修改完成" << endl;
                break;
            }
            p = p->next;
        }
        if (p == NULL)cout << "查找不到你要修改的人" << endl;
    }
    
    int main()
    {
        zz head;
        create_for_head(head);
        int choose;
        while (1)
        {
            cout << endl;
            cout << "\t|-----------------------------------|" << endl;
            cout << "\t|                                   |" << endl;
            cout << "\t|              菜单:               |" << endl;
            cout << "\t|                                   |" << endl;
            cout << "\t|         1-添加通讯录              |" << endl;
            cout << "\t|         2-查看所有联系人          |" << endl;
            cout << "\t|         3-通讯录查询              |" << endl;
            cout << "\t|         4-删除联系人              |" << endl;
            cout << "\t|         5-修改联系信息            |" << endl;
            cout << "\t|                                   |" << endl;
            cout << "\t|         0-退出                    |" << endl;
            cout << "\t|                                   |" << endl;
            cout << "\t|-----------------------------------|" << endl;
            cin >> choose;
            switch (choose)
            {
            case 1:add_person(head); continue;
            case 2:system("cls"); print_list(head);  continue;
            case 3:system("cls"); search_list(head); continue;
            case 4:system("cls"); delete_list(head); continue;
            case 5:system("cls"); change_list(head); continue;
            case 0:return 0;
            }
        }
        system("pause");
    }
    

    相关文章

      网友评论

          本文标题:字符串匹配 - BF和RK算法

          本文链接:https://www.haomeiwen.com/subject/rggjuhtx.html