当前位置：文档之家 › 数据结构串的模式匹配本课件

数据结构串的模式匹配本课件

  • 格式：pdf
  • 大小：2.13 MB
  • 文档页数：19

下载文档原格式

  / 19

合集下载

第5周串第2讲-串的模式匹配

第5周串第2讲-串的模式匹配
匹配成功
例如，设目标串s=“aaaaab”，模式串t=“aaab”。s的长度为n （n=6），t的长度为m（m=4）。BF算法的匹配过程如下。
i
s： a a a a a b
t a a a b 匹配失败：
：
i=i-j+1=1 （回退）
j
j=0 （从头开始）
i=1，j=0
i
s aaaaab
t：： a a a b
开头的k个字符 后面的k个字符
next[j]=
MAX{ k | 0<k<j，且“t0t1…tk-1” = “tj-ktj-k+1…tj-1”}
当此集合非空时
-1
当j=0时
0
其他情况
t=“aaab”对应的next数组如下:
j
0
1
t[j]
a
a
next[j]
-1
0
2
3
a
b
1
2
t0=t1="a"t0t1=t1t2="aa"
匹配失败： i=i-j+1=2（回退）
j
j=0（从头开始）
i=2，j=0
i
s a a aaa b t：： a a a b
j
匹配成功：
i=6，j=4
返回i-t.length=2
对应的BF算法如下：
int index(SqString s,SqString t)
{ int i=0, j=0;
while (i<s.length && j<t.length)
模式串t存在某个k（0＜k＜j），使得以下成立:
“t0t1…tk

数据结构—串的

数据结构—串的

数据结构一串的模式匹配实验一串的模式匹配1.程序设计简介为简化设计，程序直接利用C++字符数组作为串的存储结构。

程序提供显示串(包含主串和模式串)、计算Next[]、BF匹配、KMP匹配、重建主串、重建模式串等功能。

2.源代码〃串模式匹配的类定义Fin dSub.cpp#in cludevioma nip.h>#in cludevstri ng.h>#in clude<stdio.h>#in clude<stdlib.h>#in cludevstri ng>const maxsize=30;int In dexBF(char s[],char t[],i nt pos){int i,j,m, n;i=pos-1;j=0;m=strle n( s);n=strle n(t);while(i<m && j<n){if(s[i]==t[j]){++i；++j；}else {i=i-j+1;j=0;}}if(j>=n)return i-n+1;elsereturn -1;}void GetNext(char t[],i nt next[]){//求模式串T的next函数值并存入数组next in t j=0,k=-1;int n=strle n(t);n ext[j]=-1;while(j <n){if(k==-1||t[j]==t[k]){j++;k++; next[j]=k;}else k=n ext[k];}int IndexKMP(char s[],char t[],int next[],int pos){//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。

// 其中,T 非空,1 < pos< StrLength(S) in t i,j, n;i=pos-1;j=0;int m=strle n( s);〃s[m]='\0：n=strle n(t);//t[ n]='\0：while(i<m && jvn)if(j==-1||s[i]==t[j]){i++；j++；}〃继续比较后继字符else j=next[j];//模式串向右移动if(j>=n) return i-n+1;// 匹配成功return -1;}〃串模式匹配的测试void mai n(){ char s[maxsize]="aaabaaaabaa",t[maxsize]="aaaab"int in dex,* nex t;int choice,j,pos=0;int m,n;m=strle n( s);n=strle n(t);n ext=new int[n];GetNext(t, next);do{//显示主菜单cout«"1-BF 匹配\n";cout«"2-KMP 匹配\n";cout<<"3-查看Next[]\n";cout<<"4-显示串\n";cout<<"6-退出\n";cout«"E nter choice:";cin> >choice;switch(choice){case 1://BF 匹配cout<<"输入匹配起始位置："cin> >pos;if(pos<=m-n+1)coutvv"主串为:"vvs<v'\t'vv" 子串为:"vvtvvendl;cout«"BF 的结果:"<<endl;in dex=In dexBF(s,t,pos);if(in dex!=-1)cout<<"模式串t在主串s中的位置从第"<<index<<"个字符开始"<<endl;else cout<<"主串s中不含模式串t"<<e ndl;}else{ cout<<"位置非法，无法匹配!"<<e ndl; }break;case 2://KMP 算法cout<<"输入匹配起始位置："；cin> >pos;if(pos<=m-n+1){cout<<"主串为:"<<s<<'\t'<<" 子串为:"vvtvvendl;cout«"KMP 匹配结果:"<<endl;in dex=I ndexKMP(s,t, next,pos);if(in dex!=-1)cout<<"模式串在主串的位置从第"<<index<<"个字符开始"<<endl;elsecout<<"主串s中不含模式串t"<<e ndl;}else{ cout<<"位置非法，无法匹配!"<<e ndl; }break;case 3://显示NEXTcout<<"子串为："<<t<<endl;for(j=0;j< n;j++){cout<<" next["<<j<<"]="<< next[j]<<'\t';if((j+1)%5==0) cout<<e ndl;}cout«e ndl; break;case 4: /湿示串cout«"主串为："<<s;cout«"子串为:"<<t;cout«e ndl;break;case 6://退出cout«"结束运行!"<<endl; break;default:cout<v"lnvalid choice'n"; break;}}while(choice!=6);}3.程序运行结果:实验二求串中最长重复子串1•问题描述设串 S=”1s2 sn " , T= ”1t2 ......... tm ” 如果 rr + +\M^Dev^^Mytro ^1127 .De bug\201 i 1127A予禺为:aaaab 了 昌为=d4d4b next tl1-0 next[2J-l next(31-2 next[41-3ncm HIT %■11N ；"』”【 帥wJHT € S,则称T为S的子串。

数据结构第4章串B教学ppt

数据结构第4章串B教学ppt
严蔚敏、吴伟民编著的经典教材，详细介绍了各 种数据结构及其基本操作，包括串的实现和应用。
《算法导论》
Thomas H. Cormen等编著的经典算法教材，深 入讲解了算法设计和分析的方法，包括串的模式 匹配等算法。
MOOC课程
中国大学MOOC、Coursera等在线教育平台上 提供了大量与数据结构和算法相关的课程，可以 系统地学习相关知识和技能。
压缩串处理技术
针对大规模文本数据，研究压缩串处理技术可以减少存储 空间占用，提高处理效率，是未来发展的重要方向之一。
串的并行处理技术
利用并行计算技术加速串的处理过程，提高处理效率，是 未来研究的热点之一。需要解决并行化算法设计、并行计 算框架选择等问题。
拓展学习资源推荐
1 2 3
《数据结构（C语言版）》
Sunday算法
Sunday算法是一种简单且高效的字符串匹配算法，其核心思 想是当发现不匹配的字符时，直接跳过主串中当前字符之前 的所有字符，将模式串与主串的下一个字符进行比较。
03
串的应用举例
文本编辑中的串操作
01
02
03
字符串匹配
在文本编辑中，经常需要 查找或替换特定的字符串， 这可以通过串的匹配操作 实现。
可以使用数组下标和字 符串截取函数`substr()` 实现串的截取，如`char ch = str[2];`或 `std:string sub = str.substr(2, 4);`。
Python语言实现串的基本操作
串的定义与初始化
在Python中，串使用引号（单引号、双 引号或三引号）进行定义和初始化，如`s = 'hello'`或`s = "hello"`。的比较

数据结构第四章串ppt

数据结构第四章串ppt

昌
顺序存储结构
大
链接存储结构
学
索引存储结构
科
技 学
不讲
院
6
4.2.1 串的顺序存储结构
南• 1．顺序存储的类型定义
昌• 顺序串的类型定义与顺序表的定义相似，可以用一个字符
大 型数组和一个整型变量表示，其中字符数组存储串，整型
学 变量表示串的长度。
科 技•
如串S=“Beijing”，字符串从S.ch[0]单元开始存放，用‘\0’
{ p=(linkstring *)malloc(LEN); p->data=t[k++];
y->next=p; y=p;}
y->next=NULL; return(s);
}/* L_STRASSIGN */
26
（2）求链串长度函数L_strlen(head)：求带头结点 链串head的长度。
南 昌
图4-2
十分浪费。
8
4.2.1 串的顺序存储结构
• （2）紧凑存储。同样存
南 昌
储S="Hello boy"，用紧
大 凑格式一个地址能存四
学 个字符，如图5-3所示。 科 技 紧凑存储的优点是空间
学 利用率高，缺点是对串
院 中字符处理的效率低。
存储地址 1000 1001 1002 1003
字长为4
}/* S_STRLEN */
22
（3）顺序串的比较函数S_strcmp(s1, s2)：比较两个顺序串的 大小。若s1=s2，则函数返回0；若s1＞s2，则函数返回正数； 若s1＜s2，则函数返回负数。
/* 两个顺序串比较函数，函数返回值为0、正数或负数 */

第4章 串 数据结构课件

第4章 串 数据结构课件
saaaaabaaabsaaaaab设匹配成功发生在设匹配成功发生在sisi处则在处则在ii11趟不成功的匹配中共趟不成功的匹配中共比较了比较了ii11mm次第次第ii趟成功的匹配共比较了趟成功的匹配共比较了mm次所以总共比较了所以总共比较了iimm次因此平均比较的次数是次因此平均比较的次数是一般情况下一般情况下mnmn因此最坏情况下的时间复杂度是因此最坏情况下的时间复杂度是onmonm
）：从主串 的第pos个字符起定 （10）子串定位 ）子串定位StrIndex（s，t，pos）：从主串 的第 个字符起定 （ ， ， ）：从主串s的第 位串s中是否存在和串 值相等的子串，若存在，则返回子串t在主串 中是否存在和串t值相等的子串 在主串s中 位串 中是否存在和串 值相等的子串，若存在，则返回子串 在主串 中 第一次出现的位置，否则，返回函数值0。 第一次出现的位置，否则，返回函数值 。 例如， 例如， StrIndex（“Beijing”，“jin”，1）=4； （ ， ， ） ； StrIndex（“Beijing”，“jng”，2）=0 （ ， ， ） ）：用 串置换s串中第 （11）置换运算 ）置换运算StrReplace（s，pos，len，t）：用t串置换 串中第 （ ， ， ， ）： 串置换 pos字符开始的连续的 个字符。 字符开始的连续的len个字符 字符开始的连续的 个字符。 例如，s=“Thatфisфaфbag！”，则 例如， ！ StrReplace（s，3，2，“is”）＝“Thisфisфaфbag！” （， ， ， ）＝“ ）＝ ！ 有时用另一种置换运算StrReplace（s，t，v）表示用 串置换所有在 （ ， ， ）表示用v串置换所有在 有时用另一种置换运算 s串中出现的与 串相等的子串。 串中出现的与t串相等的子串 串中出现的与 串相等的子串。 例如， ＋＋；” 例如，s=“if（j<n）ф j＋＋；”，t=“j”，v=“i”，则 （ ） ＋＋； ， ， StrReplace（s，t，v）=“if（i<n）ф i＋＋；” （，， ） ＋＋；” （ ） ＋＋； 以上介绍的是有关串的一些基本运算， 以上介绍的是有关串的一些基本运算，利用它们可以处理关于串的 各种操作，在使用高级程序设计语言中的串类型时， 各种操作，在使用高级程序设计语言中的串类型时，对于串的基本运算 可以有不同的定义方法。 可以有不同的定义方法。

数据结构课件_第七讲(串)

数据结构课件_第七讲(串)
顺序存储实现：在顺序串中，每个字符依次 存放在一组连续的存储单元中。 串的顺序存储有两种方法：一种是每个存储 单元只存一个字符，称为非紧缩格式。第二 种，在每个存储单元中存放多个字符，称为 紧缩格式。
处理字符的速度高， 空间利用率低
节省存储空间，
处理字符速度低
顺序串的类型定义描述如下：
# define maxlen maxsize //maxsize为给定的最大长度 struct string { char ch[ maxlen ] ; //maxlen为数组中存储空间的最大数量 int len ; };
串的链式存储
链串与一般的链表类似，链串中的一个结点可以存储一 个或多个字符。 链串结点大小的选择将直接影响到串处理的效率。 存储密度=串值所占存储容量 / 实际分配存储容量 链串的类型定义如下： typedef struct Lnode { char data ; //存放字符 struct Lnode * next ; }*Linkstring ;
下课！
KMP算法
思想：设s为目标串，t为模式串，并设i指针和j指针 分别指示目标串和模式串中正待比较的字符，令i和j的初 值均为0。若有si=tj，则i和j分别增1；否则，i不变，j退回 到j=next[j]的位置（即模式串右滑），比较si和tj，若相等 则指针各增1，否则j再退回到下一个j=next[j]的位置（即 模式串继续右滑），再比较si和tj。依次类推，直到下列 两种情况之一：第一种情况是j退回到某个j=next[j]时有 si=tj，则指针各增1后继续匹配；另一种情况是j退回到j=1时，此时令指针各增1，即下一次比较si+1和t0。
操作四：strconcat（s，t）
分析：进行串连接时，由于存储空间有限，连接后的串 的长度不确定，所以存在三种情况： （1）两个串的长度之和小于最大存储量：将两个串进 行连接。 （2）两个串的长度之和大于最大存储值，但第一个串 的长度比最大存储值要小：将第二个串的部分进行连接 ，长出的部分采用截尾法处理。 （3）连接时第一个串就已将存储空间用完：不进行连 接。

《数据结构-串》课件

《数据结构-串》ppt 课件
xx年xx月xx日
• 串的基本概念 • 串的基本操作 • 串的模式匹配算法 • 串的应用 • 总结与展望
目录
01
串的基本概念
串的定义
串
由零个或多个字符组成的有限序列。
长度
串中字符的个数。
空串
长度为零的串。
串的表示
01
02
03
文本表示法
用单引号或双引号括起来 的字符序列。
文本编辑器中的串处理
在文本编辑器中，字符串处理功能通常包括字符串的查找、替换、分割、连接、大小写转 换等。这些功能可以帮助用户快速处理大量的文本数据，提高工作效率。
文本编辑器中的串处理
在文本编辑器中，字符串处理的应用场景非常广泛。例如，在编写小说或文章时，可以使 用查找和替换功能批量修改错别字或格式；在排版报纸或制作简历时，可以使用字符串分 割和大小写转换等功能快速整理文本内容。
详细描述
连接串操作需要将两个或多个已存在的字符串对象合并成一个新的字符串对象。在合并过程中，需要将前一个字 符串的结尾字符（'0'）替换为特殊字符，以便区分不同的字符串。然后，将后一个字符串的起始位置指向特殊字 符，实现两个字符串的连接。
比较串
总结词
比较串是比较两个字符串对象是否相等的过程。
详细描述
适用于模式字符串较短且主字 符串长度较小的情况。
KMP算法
总结词
高效的字符串匹配算法，能够避免不必要的比较
时间复杂度
O(n+m)，其中n是主字符串长度，m是模式字符 串长度。
详细描述
KMP算法是一种改进的字符串匹配算法，它利用 已经匹配过的部分信息，通过一个称为“部分匹 配表”或“失败函数”的辅助数据结构，跳过一 些不必要的比较，从而提高匹配效率。

串的模式匹配PPT教案学习


第3页/共38页
串的ADT定义—引用型操作
StrLength(S)
SubString( sub, commander, 4, 3) 求得sub= man SubString(sub,c om m a nde r,1,9)求得sub= c om m a nde r SubString( sub, commander, 9, 1)求得 sub = r； SubString(sub,student,5,0)求得sub= φ或 SubString(sub, beijing, 7, 2)求得sub = ?
} HString; //定长顺序存储结构下数组首元素存放串长 ，堆分配存储结构下数组各元素均存放有 效字符
第14页/共38页
Status StrAssign(HString &T, char *chars){ //chars为 常 量 char *p=chars,q; int i=0; if(T.ch) free(T.ch); while(*p++)i++; //求 chars的 长 度 T.length=i; if (!i) T.ch=NULL; else { T.ch=(char *)malloc(i*sizeof(char)); if (!(T.ch)) exit OVERFLOW; p=chars; q=T.ch; while(*p)*q++=*p++; } return OK;
第5页/共38页
2、串的最小操作子集
除串清空和销毁外StrAssign、Strcopy、Concat 、 StrLength、 SubString、StrCompare六种操 作构成一个最小操作子集。其他串操作可在这个 最小操作子集上实现,如Index(S,T,pos)

《数据结构》串》PPT课件


(5)求子串sub(s，start，len，t)。若 0≤start<length(s) 0≤len≤length(s)-start 则t中值为从串s中第start个字符起，长度为len的字符序列， 并且函数返回值为1；否则函数返回值为0。 例如，s=″data structure″, sub(s，5，5，t), 则 t=″struc″。 (6)子串定位index(s,t)函数。若在主串s中存在和t相等的 子串，则函数值为s中第一个这样的子串在主串s中的位置， 否则函数值为-1。注意，在此t不能是个空串。例如， s=″data structure″， t=″ru″, 则index(s,t)=7。 (7)替换replace(s,t,v)。操作结果是以串v替换串s中出现 的所有和非空子串t相同的不重叠子串。
4.2.3 堆存储结构
堆结构是一种动态存储结构。系统将一个容量很大的 连续空间作为多个串值可共用的空间，每当建立一个新串 时，若该串尚未赋值，它不占堆的存储空间；若要给该串 赋值，首先，从未分配的堆空间中分配给该串值要求的空 间，然后，将串值写入到分配的空间中；同样，当串的值 无意义或串值被赋空串时，原串值所占用的空间要还给堆。 所以，串的存储地址是动态分配的，一个串值的确定是通 过串在堆中的起始位置和串的长度实现的。为此，串名和 串值之间要建立一个对照表。例如图4.5，所示为对照表和 存放字符串的堆。
/* 若0≤start<length(s)并且0≤len≤length(s)-start，则 将串s中从第start个字符起，长度为len的字符序列复制到t中，函 数返回1；否则函数返回0 */
{ int n,i; if(start<0||start>=(n=length(s))) return(0); if(len<0||len+start>n) return(0); for(i=0;i<len,i++) t[i]=s[start+i]; s[m+n]= ’\0’; /* 子串串结束标志 */ return(1); }

数据结构课件(串)

第四章 串
4.1 串的 定义
4.2 串的 表示和 实现
4.3 串的 模式匹 配算法
4.4 串应 用
数据结构
第四章 串
2019年12月22日星期日
1
第四章 串
第四章 串
4.1 串的 定义
4.2 串的 表示和 实现
4.3 串的 模式匹 配算法
4.4 串应 用
串的逻辑结构和线性表极为相似，区别仅在于串的 数据对象约束为字符集。
5
4.1 串的定义
第四章 串
4.1 串的 定义
4.2 串的 表示和 实现
4.3 串的 模式匹 配算法
4.4 串应 用
串的抽象数据类型的定义
StrCompare (S, T) 初始条件：串S和T存在。 操作结果：若S >T，则返回值 >0；若S =T，
则返回值 =0；若S <T，则返回值<0。
StrLength (S) 初始条件：串S存在。 操作结果：返回S的元素个数，称为串的长度。
然而，串的基本操作和线性表有很大差别。在线性 表的基本操作中，大多以“单个元素”作为操作对象，
如：在线性表中查找某个元素、求取某个元素、在 某个位置上插入一个元素和删除一个元素等；
而在串的基本操作中，通常以“串的整体”作为操 作对象，
如：在串中查找某个子串、求取一个子串、在串的 某个位置上插入一个子串以及删除一个子串等。
4.3 串的 模式匹 配算法
4.4 串应 用
串的逻辑结构和线性表的区别:
1. 串的数据对象约束为字符集。 2. 线性表的基本操作大多以“单个元素”为操作对 象，而串的基本操作通常以“串的整体”作为操作对象。
对于串可以定义以下运算：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。