字符串匹配 - BF和RK算法

字符串匹配有很多种算法，今天在这里先介绍两种比较简单的算法：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");
}