字符串匹配有很多种算法,今天在这里先介绍两种比较简单的算法: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
这样,我们就不必每次都计算子串的哈希值了,而是可以根据上一个子串计算得到。这样,我们减少了对内存的访问次数,同时与模式串的比较也非常高效。
用散列冲突减少计算负担
按照上面的逻辑,字符串的散列值不会产生散列冲突。但是这也带来了一个问题,如果模式串的长度非常长,比如达到 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");
}
网友评论