Access denied | www.slyar.com used Cloudflare to restrict access
Please enable cookies.
What happened?
The owner of this website (www.slyar.com) has banned your access based on your browser's signature (43f60c-ua98).分别计算下列模式串的next数组值_中华文本库
串的next数组值求法与nextval求法 - 记得大学时自己也总结出了这种算法的,手动计算,数据结构的书都丢了,还好在网上找会 了同样的算法 特记下: int get_...
求串的next函数值的方法 - 模式串‘aaaab’和‘adabbadada’ next和nextval数组值 记得大学时自己也总结出了这种算法的,手动计算,数据结构的书都丢了,还好在网上...
模式串 t=‘abcaabbcabcaabdab’ ,该模式串的 next 数组的值为( ),nextval...】 14.下列算法实现求采用顺序结构存储的串 s 和串 t 的一个最长公共子串。...
详解KMP算法中Next数组的求法 - 详解 KMP 算法中 Next 数组的求法 例如: 1 2 3 4 5 6 7 8 模式串 next 值 a b a a b c a c 0 1 1 2 ...
模式串 t=‘abcaabbcabcaabdab’ ,该模式串的 next 数组的值为( ),nextval...中的互异的非平凡子串(非 空且不同于 S 本身)的个数为( )【中科院计算所...
“abcaabbcabcaabdab” ,该模式串的 next 数组值...4 的结点的个数分别为 4、3、2、1,则树 T 的...棵哈夫曼树, 并计 (本题 8 分) 算其带权路径...
(×)串长度是指串中不同字符的个数。 2. (×)数组可以看成是线性结构的一...1)计算模式 p 的 next 函数值 (3 分))利用 KMP 算法进行模式匹配...
·2i(i = 0, 1, ?, n-1)的值并分别存入数组 a[arrsize]的各个分量 ...试按上 述定义的结构改写求模式串的 next 函数值的算法。 注:根据同学们的...
算法详解(NEXT 数组修正的补充) KMP 算法详解(NEXT...但模式串比较到了 12 位的时候(下标为 11) next...所以说对于某个字符串,在算出 next[i]的值后,不...
KMP算法中next数组的计算方法研究_自然科学_专业资料...值定义如下 : 串匹配算 法中, 经典的有简单模式...两种 不同的计算 方式 对应 了两 种不 7,],1...一步一步走向天边
求nextval数组值的简便方法
求nextval数组值的第二种方法
1.第一位的nextval值必定为0，第二位如果于第一位相同则为0，如果不同则为1。
2.第三位的next值为1，那么将第三位和第一位进行比较，均为a，相同，则，第三位的nextval值为0。
3.第四位的next值为2，那么将第四位和第二位进行比较，不同，则第四位的nextval值为其next值，为2。
4.第五位的next值为2，那么将第五位和第二位进行比较，相同，第二位的next值为1，则继续将第二位与第一位进行比较，不同，则第五位的nextval值为第二位的next值，为1。
5.第六位的next值为3，那么将第六位和第三位进行比较，不同，则第六位的nextval值为其next值，为3。
6.第七位的next值为1，那么将第七位和第一位进行比较，相同，则第七位的nextval值为0。
7.第八位的next值为2，那么将第八位和第二位进行比较，不同，则第八位的nextval值为其next值，为2。
在“aaaab”内进行验证。
求next数组nextval值
KMP算法(求模式串的next及nextval值)
KMP中next和nextval算法简析
KMP算法中next数组、nextval数组的手工计算
KMP算法中next和nextval数组的求解
详解又详解KMP中的next和nextval的算法
Next 值与 Nextval 值的计算
手动计算KMP算法的Next数组与NextVal数组
简单易懂next值nextval计算
没有更多推荐了，令s=‘aaab’，t=‘abcabaa’。试分别求出它们的next函数值和nextval函数值，并由
var sogou_ad_id=731549;
var sogou_ad_height=160;
var sogou_ad_width=690;&|&&|&&|&&|&&
当前位置： >
串-第4章-《数据结构题集》答案解析-严蔚敏吴伟民版
作者：迷路的国王 & 来源：转载 &
摘要: 习题集解析部分第4章串——《数据结构题集》-严蔚敏.吴伟民版
源码使用说明
链接??? 《数据结构-C语言版》（严蔚敏,吴伟民版）课本源码+习题集解析使用说明
课本源码合辑
链接??? 《数据结构》课本源码合辑
习题集全解析
链接??? 《数据结构题集》习题解析合辑
相关测试数据下载 链接?数据包
本习题文档的存放目录：数据结构\▼配套习题解析\▼04串
习题集解析部分
——《数据结构题集》-严蔚敏.吴伟民版
& & & &源码使用说明&&链接???&《数据结构-C语言版》（严蔚敏,吴伟民版）课本源码+习题集解析使用说明
& & & &课本源码合辑&&链接???&《数据结构》课本源码合辑
& & & &习题集全解析&&链接???&《数据结构题集》习题解析合辑
& & & 相关测试数据下载 &链接? 数据包
& & & 本习题文档的存放目录：数据结构\▼配套习题解析\▼04 串
& & & 文档中源码的存放目录：数据结构\▼配套习题解析\▼04 串\▼习题测试文档-04
& & & 源码测试数据存放目录：数据结构\▼配套习题解析\▼04 串\▼习题测试文档-04\Data
一、基础知识题
4.1?简述空串和空格串（或称空格符串）的区别。
4.2?对于教科书4.1节中所述串的各个基本操作，讨论是否可由其他基本操作构造而得，如何构造？
4.3?设s = ‘I AM A STUDENT’，t = ‘GOOD’，q = ‘WORKER’。
求：StrLength(s)，StrLength(t)，SubString(s, 8, 7)，SubString(t, 2, 1)，Index(s, ‘A’)，Index(s, t)，Replace(s, ‘STUDENT’, q)，Concat(SubString(s, 6, 2), Concat(t, SubString(s, 7, 8)))。
4.4?已知下列字符串
& & a = ‘THIS’,　f = ‘A SAMPLE’,　c = ‘GOOD’,　d = ‘NE’,　b = ‘ ’.
& & s = Concat(a, Concat(SubString(f, 2, 7), Concat(b, SubString(a, 3, 2)))),
& & t = Replace(f, SubString(f, 3, 6), c),
& & u = Concat(SubString(c, 3, 1), d),
& & g = ‘IS’,
& & v = Concat(s, Concat(b, Concat(t, Concat(b, u)))),
& 试问：s，t，v，StrLength(s)，Index(v, g)，Index(u, g)各是什么？
4.5?试问执行以下函数会产生怎样的输出结果？
&&& void demonstrate()
&&&&&&& StrAssign(s, ‘THIS IS A BOOK’);
&&&&&&& Replace(s, SubString(s, 3, 7), ‘ESE ARE’);
&&&&&&& StrAssign(t, Concat(s, ‘S’));
&&&&&&& StrAssign(u, ‘XYXYXYXYXYXY’);
&&&&&&& StrAssign(v, SubString(u, 6, 3));
&&&&&&& StrAssign(w, ‘W’);
&&&&&&& printf(‘t=’, t, ‘v=’, v, ‘u=’, Replace(u, v, w));
& & }//demonstrate
4.6?已知：s = ‘(XYZ)+*’,t = ‘(X+Z)*Y’。试利用联接、求子串和置换等基本运算，将s转化为t。
4.7?令s = ‘aaab’,t = ‘abcabaa’,u = ‘abcaabbabcabaacbacba’。试分别求出它们的next函数值和nextval函数值。
4.8?已知主串s = ‘ADBADABBAABADABBADADA’,
&&&&&&& 模式串pat = ‘ADABBADADA’,
& 写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。
4.9?在以链表存储串值时，存储密度是结点大小和串长的函数。假设每个字符占一个字节，每个指针占4个字节，每个结点的大小为4的整数倍，已知串长的分布函数为f(l)且，求结点大小为4k，串长为l时的存储密度d(4k, l)（用公式表示）。
二、算法设计题
& & 在编写4.10至4.14题的算法时，请采用StringType数据类型：
&&& StringType是串的一个抽象数据类型，它包含以下五种基本操作：
&&& void StrAssign (StringType &t, StringType s);　 &&//将s的值赋给t。s的实际参数可以是串变量或者串常量（如：‘abcd’）。
&&& int StrCompare (StringType s, StringType t);　　&//比较s和t。若s&t，返回值&0；若s=t，返回值=0；若s&t，返回值&0。
&&& int StrLength (StringType s);　　　　　　　　　　&//返回s中的元素个数，即该串的长度。
&&& StringType Concat (StringType s, StringType t); &&//返回由s和t联接而成的新串。
&&& StringType SubString (StringType s, int start, int len) ;&//当1≤start≤StrLength(s)且0≤len≤StrLength(s)-start+1时，返回s中第start个字符起长度为len的子串，否则返回空串。
4.10?编写对串求逆的递推算法。
4.11?编写算法，求得所有包含在串s中而不包含在串t中的字符（s中重复的字符只选一个）构成的新串r，以及r中每个字符在s中第一次出现的位置。
4.12?编写一个实现串的置换操作Replace(&S, T, V)的算法。
4.13?编写算法，从串s中删除所有和串t相同的子串。
4.14?利用串的基本操作以及栈和集合的基本操作，编写“由一个算术表达式的前缀式求后缀式”的递推算法（假设前缀式不含语法错误）。
& & & & 在编写4.15至4.20题的算法时，请采用教科书4.2.1节中所定义的定长顺序存储表示，而不允许调用串的基本操作。
4.15?编写算法，实现串的基本操作StrAssign(&T, chars)。
4.16?编写算法，实现串的基本操作StrCompare(S, T)。
4.17?编写算法，实现串的基本操作Replace(&S, T, V)。
4.18?编写算法，求串s所含不同字符的总数和每种字符的个数。
4.19?在串的定长顺序存储结构上直接实现4.11题要求的算法。
4.20?编写算法，从串s中删除所有和串t相同的子串。
4.21?假设以结点大小为1（且附设头结点）的链表结构表示串。试编写实现下列六种串的基本操作StrAssign，StrCopy，StrCompare，StrLength，Concat和SubString的函数。
4.22?& 假设以块链结构表示串。试编写将串s插入到串t中某个字符之后的算法（若串t中不存在此字符，则将串s联接在串t的末尾）。
4.23?假设以块链结构作串的存储结构。试编写判别给定串是否具有对称性的算法，并要求算法的时间复杂度为O(StrLength(S))。
& & & & 在编写4.24至4.26题的算法时，请采用教科书4.2.2节中所定义的堆分配存储表示。
4.24?试写一算法，在串的堆存储结构上实现串基本操作Concat(&T, s1，s2)。
4.25?试写一算法，实现堆存储结构的串的置换操作Replace(&S, T, V)。
4.26?试写一算法，实现堆存储结构的串的插入操作 StrInsert(&S, pos, T)。
4.27?当以教科书4.2.1节中定义的定长顺序结构表示串时，可如下所述改进定位函数的算法：先将模式串t中的第一个字符和最后一个字符与主串s中相应的字符比较，在两次比较都相等之后，再依次从t的第二个字符逐个比较。这样做可以克服算法Index（算法4.5）在求模式串’akb’（ak表示连续k个字符’a’）在主串’anb’（k≤n）中的定位函数时产生的弊病。试编写上述改进算法，并比较这两种算法在作Index（’anb’,’akb’）运算时所需进行的字符间的比较次数。
4.28?假设以结点大小为1（带头结点）的链表结构表示串，则在利用next函数值进行串匹配时，在每个结点中需设三个域：数据域chdata、指针域succ和指针域next。其中chdata域存放一个字符；succ域存放指向同一链表中后继结点的指针；next域在主串中存放指向同一链表中前驱结点的指针；在模式串中，存放指向当该结点的字符与主串中的字符不等时，在模式串中下一个应进行比较的字符结点（即与该字符的next函数值相对应的字符结点）的指针，若该节点字符的next函数值为0，则其next域的值应指向头结点。试按上述定义的结构改写求模式串的next函数值的算法。
4.29?试按4.28题定义的结构改写串匹配的改进算法（KMP算法）。
4.30?假设以定长顺序存储结构表示串，试设计一个算法，求串s中出现的第一个最长重复子串及其（第一次出现的）位置，并分析你的算法的时间复杂度。
4.31?假设以定长顺序存储结构表示串，试设计一个算法，求串s和串t的一个最长公共子串，并分析你的时间复杂度。若要求第一个出现的最长公共子串（即它在串s和串t的最左边的位置上出现）和所有的最长公共子串，讨论你的算法能否实现。
版权所有 IT知识库 CopyRight (C)
IT知识库 IT610.com , All Rights Reserved.