邯郸网站优化建设网站建设属于什么税种

当前位置： 首页 > news >正文

邯郸网站优化建设,网站建设属于什么税种,网站留言板html代码,一个正规的网站建设公司目录 一. 一些术语 二. 串的类型定义 #xff08;1#xff09;串的顺序存储结构 #xff08;2#xff09;串的链式存储结构 三. 串的模式匹配算法 #xff08;1#xff09;BF算法 #xff08;2#xff09;KMP算法 四. 案例实现 串(String)—零个或多个任意字符…目录 一. 一些术语 二. 串的类型定义 1串的顺序存储结构 2串的链式存储结构 三. 串的模式匹配算法 1BF算法 2KMP算法 四. 案例实现 串(String)—零个或多个任意字符组成的有限序列。 一. 一些术语 子串串中任意个连续字符组成的子序列称为该串的子串 主串包含子串的串相应地称为主串 字符位置字符在序列中的序号为该字符在串中的位置 子串位置子串第一个字符在主串中的位置 空格串由一个或多个空格组成的串与空串不同 例如给定字符串a、b、c、daBEIb JINGcBEIJINGdBEI JING 它们的长度是 3478 c的子串是ab d的子串是ab a在c中的位置是1a在d中的位置是1 b在c中的位置是4a在d中的位置是5 串相等当且仅当两个串的长度相等并且各个对应位置上的字符都相同时这两个串才是相等的。 二. 串的类型定义 串的抽象数据类型定义同线性表只不过处理对象是字符。 ADT String{数据对象:D{ ai | ai ∈ElemSet, i1,2..,n, n≥0 }数据关系:R1 { ai-1, ai | ai-1, ai∈D, i2,…,n }基本操作:StrAssign (T,chars) //串赋值StrCompare (S,T) //串比较StrLength (S) //求串长Concat(T,S1,S2) //串连结Index(S,T,pos) //求子串的位置…还有其他操作… }ADT String与前面完全相同串也可分为顺序串和链串。 1串的顺序存储结构 #define MAXLEN 255 typedef struct{char ch[MAXLEN1]; //存储串的一维数组int length; //串的当前长度 }SString; 说明实际存储时通常是char ch[MAXLEN1]然后把第一个位置空出这在处理一些问题时会简便一些。 2串的链式存储结构 和链表不同的是我们可以在一个结点有多个数据元素这种结点我们称之为块可以显著提高存储密度。 # define CHUNKSIZE 80 //块的大小可自定义 typedef struct Chunk{char ch[CHUNKSIZE];struct Chunk *next; }Chunk; //定义一个块的结点typedef struct{Chunk *head,*tail; //串的头指针和尾指针int curlen; //串的当前长度 }LString; //字符串的块链结构 三. 串的模式匹配算法 模式匹配算法的目的确定主串中所含子串(模式串)第一次出现的位置 (定位)。针对模式匹配问题我们有BF算法(Brute-Force, 又称古典的、经典的、朴素的、穷举的)和KMP算法速度快下面介绍这两种算法。 1BF算法 BF算法采用的基本思想是穷举法。将主串的第pos个字符和模式串的第一个字符比较。若相等继续逐个比较后续字符若不等从主串S的下一字符起重新与模式串T的第一个字符比较。例如目标串的长度m6模式串的长度n4。则先将目标串的1-4位与模式串对应1-4位逐个比较i1,j1然后起始位置加1将目标串的2-5位与模式串对应1-4位逐个比较i2,j1最后将目标串的3-6位与模式串对应位逐个比较i3,j1。如果这时候还没有找到则返回0表示目标串中不存在对应的模式串。 这里还需要牵扯到一个回溯的问题模式串T比较到第j位时发现匹配不成功这个时候要进入下一轮匹配。模式串T中j直接置1前面讲了字符串第一个索引为0的位置空出来那么目标串S中i应该置多少呢上一轮匹配中模式串T从1到j位往后挪了j-1步所以目标串S中第一个被比较的字符所有是i-(j-1)然后现在我们要进入下一轮循环从这个字符的下一个字符开始因此回溯的位置应该是i-(j-1)1i-j2。 当匹配成功时模式串T中指针j指向的位置索引应该是1T.length最后一个元素的下一个元素为空退出循环在此之前所有字符都匹配成功。所以返回的索引值应该是此刻的i值减去模式串的长度i-T.length。 下面给出BE算法的代码描述 int Index_BF(SString S, SString T, int pos){int ipos, j1; //从主串第pos位开始查找while (iS.length jT.length) {if (S.ch[i]T.ch[j]) {i; j;} //本字符对应位置匹配成功主串和子串依次匹配下一个字符else {ii-j2;j1;} //本字符匹配不成功主串、子串指针回溯重新开始下一次匹配}if (jT.length) return i-T.length; //这个时候在主串中找到了子串返回匹配的第一个字符的下标 else return 0; //直到所有循环结束仍没有在主串中找到子串模式匹配不成功 }最后讨论算法的时间复杂度如果主串S子串T的长度为m,n最多需要进行的循环次数是m-n1次每次比较n次则最坏情况下的时间复杂度是O(m-n1*n。若nm可简化为Omn。 2KMP算法 此部分难度较大建议看王道的视频动画演示这里总结一下怎么求next数组和nextval数组 4.2_2_KMP算法_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1b7411N798?p36vd_source7bf292964a807d18168b0c665fed431cnext数组的求法手算练习 next[1]都无脑写0next[2]都无脑写1其他next在不匹配的位置前划一根美丽的分界线模式串一步一步往后退直到分界线之前“能对上”或模式串完全跨过分界线为止。此时j指向哪儿next数组值就是多少。 例如对于字符串google googlenext[0]next[1]next[2]next[3]next[4]next[5]next[6]011121 KMP算法实际上就是改变了指针的回溯位置主串中指针不回溯子串中指针回溯的位置由next数组确定。next数组的作用就是当子串的第j个字符失配时从子串的第next[i]的继续往后匹配而不一定非要从1开始。 nextval数组求解 在此基础上进一步优化next数组具体操作是首先解出next数组然后用以下步骤优化 nextval [1]0; for (int j2; jT.length; j) {if (T.ch[next [j]]T.ch[j])nextval[j]nextval[next[j]];elsenextval[j]next[j]; }例如对以下字符串 ababbanext[0]next[1]next[2]next[3]next[4]next[5]next[6]next数组011234nextval数组010104 四. 案例实现 对于病毒检测患病时患者的DNA中包含病毒的DNA。但是病毒的DNA是环状的也就是说假如aab是病毒的DNA则ababaa都是病毒的DNA。如图 算法的主要思想如下 对于每一个待检测的任务假设病毒DNA序列的长度是m因为病毒DNA序列是环状的为了线性取到每个可行的长度为m的模式串可将存储病毒DNA序列的字符串长度扩大为2m将病毒DNA序列连续存储两次。然后循环m次依次取得每个长度为m的环状字符串将此字符串作为模式串将人的DNA序列作为主串调用BF算法进行模式匹配。只要匹配成功即可中止循环表明该人感染了对应的病毒;否则循环m次结束循环时可通过BF算法的返回值判断该人是否感染了对应的病毒。