Dotcpp  >  编程教程  >  字符串相关  >  字符串匹配实例讲解

字符串匹配实例讲解

点击打开在线编译器,边学边练

本篇主要讲字符串匹配以及字符串算法中三个主要算法的一些内容,帮助大家理解。

一、基本概念

字符串匹配问题

假设文本是一个长度为n的数组T[1…n],而模式是一个长度为m的数组P[1…m],其中m≤n,进一步假设P和T的元素都是来自一个有限的字母集∑的字符。数组T和P通常被称为字符串。

如果0≤s≤n−m,并且T[s+1…s+m]=P[1…m],那么称模式P在文本T中出现过,且偏移为s。如果P在T中以偏移s出现,那么称s为有效偏移,否则为无效偏移。

字符串匹配问题就是在T中找到P的所有有效偏移s。


二、字符串匹配算法

字符串匹配算法

(1)BF算法

BF算法,即暴风(Brute Force)算法,也叫暴力破解法,是普通的模式匹配算法。

算法思想:将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。

时间复杂度:O(n*m)

int BF_match(char *T,char *P){
	int i = 0, j = 0;
	for (; T[i] != '\0' && P[j] != '\0'; i++)
		if (T[i] == P[j])
			j++;
		else
		{
			i -= j;
			j = 0;
		}
	if (P[j] == '\0') return i - j;
	else return -1;
}

(2)BM算法

Boyer-Moore字符串搜索算法是一种非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年。

算法思想:用坏字符表(BS)记录每个字符在模式串中最后的位置,用好后缀表(GS)记录模式串中与后缀匹配的位置,当匹配失败时,取二者中最大的位移量移动,减少字符对比次数

时间复杂度:O(n/m)~O(n+m)


(3)KMP算法

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的。

算法思想:用next数组存储当前字符之前的字符串前、后缀最长公共元素长度,匹配失败时通过next数组偏移

时间复杂度:O(n+m)


算法

效率

优点

缺点

适用环境

BF

O(n*m)

简单实现

效率低

仅简单字符串匹配,不要求效率的情况

BM

O(n/m)~O(n+m)

效率极高

前期准备工作量大

文本串较长的情况

KMP

O(n+m)

效率高、稳定性强

无明显短板

要求稳定性或文本串较短的情况



知识点标签:字符串


本文固定URL:https://www.dotcpp.com/course/1009

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)