[考研系列之数据结构]线性表之字符串

基本概念

串(字符串)  由0个或多个字符组成的有限序列,例如s="hello world"
串名  上例中的s
子串  某串任意连续字符组成的子序列,称为此字符串的子串
空串  0个字符的串,s=""
空格串  由一个或多个字符组成的串

模式匹配算法

作用 定位某子串T在字符串S中的位置
主串 S
模式串  T

针对模式匹配算法从简到难我们需要了解两种算法:

[1] 朴素的模式匹配算法

[2] KMP匹配算法

朴素的模式匹配算法:

所谓朴素就是简单,这是一种简单的模式匹配。让我们从一个栗子来看朴素的模式匹配算法是如何进行的。

主串S="ababcabcacbab"

模式串T="abcac"

直接截图严书了。

对于朴素的模式匹配算法,我们依次将T的第j个字符和S的第i个字符比较,如果

T[i]==S[j] 匹配成功  ++i;++j;进行下一个字符的匹配
T[i]!=S[j]

匹配失败

T需要重新从第0个字符开始匹配
S的j也需要回溯到某个位置

这里关键是j应该回退到那个位置。

上面的草图画出了S和T在某个位置匹配失败了,那么i需要退回到0而j应该退回到x+1;通过很简单的计算

j-x=i

x+1=j-i+1

下面,什么时候算法结束?

当T或者S已经匹配了最后一个字符的时候,程序结束。当T匹配到最后一个字符且仍然匹配成功那么整个匹配就是成功的,反之失败。

下面给出C++风格的代码:

int index(String S,String T)

{

int i=0;

int j=0;

while(i<T.length&&j<S.length)

{

if(T[i]==S[j]) //本次字符匹配成功

{

++i;++j;

}

else //本次字符匹配失败

{

j=j-i+1;i=0;

}

}

if(i==T.length) //成功匹配

return j-i;

return 0;

}

KMP匹配算法

对于朴素的匹配算法,在最差的情况下,它只能取得O(S.length*T.length)的算法复杂度,而基于朴素模式匹配算法的KMP能在O(T.length+S.length)内完成。

让我们先想想,朴素的匹配算法最耗时的操作是什么?

是j的回溯,j需要回溯到j-i+1的位置进行下一轮匹配。那么如何能减少j的回溯长度呢?依然以朴素匹配算法中的实例为栗子。

我们看到T匹配到"abca"时,匹配失败,如果按照朴素匹配算法,下面S会跳到"bcbb..."的第二个位置进行匹配,但是很明显,第一次就会匹配失败,第三次"cbb..."依然会在第一次匹配的时候失败,那么这两轮匹配其实是没有意义的,因为从模式串T看来,由于是在第四个位置匹配失败的,但是它前面的三个位置是匹配成功的,它知道下一轮匹配的S的首字符是T[1]="b",再下次是T[2]="C"。那么,我们通过研究T的规律是可以减少回溯减少不必要的匹配轮数的。

下面正式进入KMP算法。首先来一段理论的说明:

KMP匹配算法主要步骤有两步

[1] 求next数组

[2] 利用next数组进行匹配

下面首先让我们看看next数组

含义:next[j]表示当T[j]和S[i]失配的时候,在T中需要和S[i]重新比较的字符的位置,也就是会比较T[next[j]]和S[i]的关系

定义:

[待续]

[考研系列之数据结构]线性表之字符串,布布扣,bubuko.com

时间: 06-01

[考研系列之数据结构]线性表之字符串的相关文章

[考研系列之数据结构]线性表之栈

?基本概念 栈的定义 限定仅在表尾进行插入或删除的线性表 组成 栈顶 栈底 基本操作 入栈(PUSH) 往栈中插入一个元素 弹栈(POP) 从栈顶删除一个元素 栈的表示 顺序栈 链栈 对于顺序栈,有两个指针base和top base指向栈底 top指向栈顶 对于栈的一些基本情况: 栈不存在时候 base=NULL 栈为空时  top=base 栈的长度 top-base 链栈略过. 栈的应用 1 数制转换 数制转换我们使用一种称之为"辗转相除法"的算法.此算法的基本原理基于: N=(N

[考研系列之数据结构]线性表概述

1.脑图 2.表示方法 按照数据结构概述所说,线性表有两种表示方法分别是顺序表示和链式表示,链表就是链式表示的典型. 我们知道链式表示是分配了n块内存空间,可以认为彼此不连续,所以不能用偏移量去定位每个元素. 下面就先说最简单的单向链表: 如果每个数据元素能有一个指针指向下一个元素的话,那么只需要知道第一个数据元素就能一个一个的遍历整个链表了,这就是单向链表. 对于每个链表元素我们称之为节点,每个节点都有两个域:数据域&指针域 数据域就是数据元素所在的区域,而指针域则是存储指向另一个节点的指针的

[考研系列之数据结构]线性表之队列

基本概念 队列的定义 队列是一种只能在表的一头插入,另一头删除的线性表,简而言之具有FIFO的特性 组成 队头 队尾 扩展 双端队列 只能在两端进行删除插入操作的线性表 实现 链队列 顺序队列 循环队列 循环队列 循环队列是将顺序队列臆造成一个环,如图 循环队列有以下参数 front 指向队头的指针 rear 指向队尾的指针 SIZE 循环最大队列长度 对于循环队列,初始状态的时候 front=rear=0; 每次insert的时候 Insert((front++)%SIZE); 那么,当循环队

[考研系列之数据结构]线性表之链表

1.链表分类 通过线性表概述,我们知道了链表这样一种数据结构,它又分成三类,分别是 单向链表 循环链表 双向链表 单向链表 单向链表的指针域只有一个指向下一个节点的指针,需要注意几点: 1.头指针--指向第一个节点 2.最后一个结点的指针指向NULL 3.头结点--在链表的第一个结点之前附设一个结点,它的数据域为空 所以,我们看到:  单向链表为空的<=>链表有且只有一个头结点<=>头结点的指针指向NULL 循环链表 循环链表和单向链表最大的不同就是:最后一个结点的指针不再指向NU

数据结构线性表链表的C语言实现

                                                                                      数据结构线性表链表的C语言实现      说明:线性表是一种最简单的线性结构,也是最基本的一种线性结构,所以它不仅是学习中的重点,也是应用开发非常常用的一种数据结构.它可以分为顺序表和链表.它的主要操作是数据元素的插入,删除,以及排序等.接下来,本篇文章将对线性表链表的基本操作和运用进行详细的说明(包含在源代码的注释中),并给

数据结构-线性表(2)

线性表定义: 线性表是最基本.最简单.也是最常用的一种数据结构.线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的.线性表的逻辑结构简单,便于实现和操作.因此,线性表这种数据结构在实际应用中是广泛采用的一种数据结构. 存储空间是否连续: 一.顺序表的特点是逻辑上相邻的数据元素,物理存储位置也相邻,并且,顺序表的存储空间需要预先分配. 优点: (1)方法简单,各种高级语言中都有数组,容易实现. (2)不用为表示节点间的逻辑关系而增加额外的存储开

数据结构&gt;&gt;线性表【注意】--&gt;链表求A-B(原A与B都递增,求完的A-B不改变A原来的顺序)

/*关于链表的题目 * A.B是两个递增有序的单链表,元素个数分别是m和n,求 * 集合A-B,并将结果保存在A中,且仍然保持递增有序. * converge_ab */ #include <iostream.h> using namespace std; typedef struct lnode{ int data; struct lnode * next; }lnode; int main(){ lnode * create_chain(int num,int interval,int s

java实现数据结构-线性表-顺序表,实现插入,查找,删除,合并功能

package 顺序表; import java.util.ArrayList; import java.util.Scanner; public class OrderList { /** * @param args * @author 刘雁冰 * @2015-1-31 21:00 */ /* * (以下所谓"位置"不是从0开始的数组下标表示法,而是从1开始的表示法.) * (如12,13,14,15,16数据中,位置2上的数据即是13) * * 利用JAVA实现数据结构-线性表-顺

Java数据结构-线性表之单链表LinkedList

线性表的链式存储结构,也称之为链式表,链表:链表的存储单元可以连续也可以不连续. 链表中的节点包含数据域和指针域,数据域为存储数据元素信息的域,指针域为存储直接后继位置(一般称为指针)的域. 注意一个头结点和头指针的区别: 头指针: 指向链表的第一个节点的指针,若链表有头结点,则是指向头结点的指针: 头指针具有标识作用,所以常用头指针作为链表的名字: 不论链表是否为空,头指针都不为空: 是链表的必要元素. 头结点: 头结点是为了操作的统一和方便而设立的,放在第一个元素节点的前面,其数据域一般无意