天地不仁以万物为刍狗
next nextval求值
参考教材，清华大学，严蔚敏，C语言版，数据结构
求next[j]时，查找next[j]之前是否有前缀和后缀相等的字符串，若没有，则next[j]=1，如果存在前缀和后缀相同的字符串，则next[j]的值取前缀码的后一位。
next[2]=1；j=2之前有a，没有相同的前缀和后缀
next[3]=1；j=3之前有ab，没有相同的前缀和后缀
next[4]=2；j=4 之前有aba，有相同串a，所以next[4]=1+1=2
next[5]=2；j=5之前有abaa，有相同串a，所以next[5]=1+1=2
next[6]=3；j=6之前有abaab，有相同串ab，所以next[6]=2+1=3
next[7]=1；j=7之前有abaabc，没有相同前缀和后缀，所以next[7]=1
next[8]=2；j=7之前有abaabca，有相同串a，所以next[7]=1+1=2
nextval[j]
比较s[j]与s[next[j]]的值，如果s[j]=s[next[j]]，nextval[j]=nextval[next[j]]，不相等，则nextval[j]=next[j]
nextval[1]=0;
nextval[2]=1; s[2]=b
s[1]=a；nextval[2]=next[2]=1；
nextval[3]=0; s[3]=a
== s[1]=a；nextval[3]=nextval[1]=0；
nextval[4]=2; s[4]=a
s[2]=b；nextval[4]=next[4]=2；
nextval[5]=1; s[5]=b
== s[2]=b；nextval[5]=nextval[2]=1；
nextval[6]=3;
s[3]=a；nextval[6]=next[6]=3；
nextval[7]=0; s[7]=a
== s[1]=a；nextval[6]=nextval[1]=0；
nextval[8]=2; s[8]=c
s[2]=b；nextval[6]=next[8]=0；
没有更多推荐了，求字符串adabbadada的next和nextval的函数值_百度知道
求字符串adabbadada的next和nextval的函数值
求字符串adabbadada的next和nextval的函数值
我有更好的答案
　int get_nextval(SString T,int &nextval[ ]){　　//求模式串T的next函数修正值并存入数组nextval。　　i=1; nextval[1]=0; j=0;　　while(i&T[0]){　　if(j==0||T[i]==T[j]){　　++i;++j;　　if (T[i]!=T[j]) nextval[i]=j;　　else nextval[i]=nextval[j];　　}　　else j=nextval[j];　　}　　}//get_nextval　　根据这段程序来求nextval的值是可以方便计算出来，但如果是应付考研试题或者期末考试就有点麻烦了。而如果记住我推荐的方法，那么任何时候都可以很方便地求解nextval了。　　首先看看next数组值的求解方法。　　例如： 模式串 a b a a b c a c　　next值 0 1 1 2 2 3 1 2　　nextval值　　next数组的求解方法是：第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。　　看起来很令人费解，利用上面的例子具体运算一遍。　　1.前两位必定为0和1。　　2.计算第三位的时候，看第二位b的next值，为1，则把b和1对应的a进行比较，不同，则第三位a的next的值为1，因为一直比到最前一位，都没有发生比较相同的现象。　　3.计算第四位的时候，看第三位a的next值，为1，则把a和1对应的a进行比较，相同，则第四位a的next的值为第三位a的next值加上1。为2。因为是在第三位实现了其next值对应的值与第三位的值相同。　　4.计算第五位的时候，看第四位a的next值，为2，则把a和2对应的b进行比较，不同，则再将b对应的next值1对应的a与第四位的a进行比较，相同，则第五位的next值为第二位b的next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的值相同。　　5.计算第六位的时候，看第五位b的next值，为2，则把b和2对应的b进行比较，相同，则第六位c的next值为第五位b的next值加上1，为3，因为是在第五位实现了其next值对应的值与第五位相同。　　6.计算第七位的时候，看第六位c的next值，为3，则把c和3对应的a进行比较，不同，则再把第3位a的next值1对应的a与第六位c比较，仍然不同，则第七位的next值为1。　　7.计算第八位的时候，看第七位a的next值，为1，则把a和1对应的a进行比较，相同，则第八位c的next值为第七位a的next值加上1，为2，因为是在第七位和实现了其next值对应的值与第七位相同。　　在计算nextval之前要先弄明白，nextval是为了弥补next函数在某些情况下的缺陷而产生的，例如主串为“aaabaaaab”、模式串为“aaaab”那么，比较的时候就会发生一些浪费的情况：比较到主串以及模式串的第四位时，发现其值并不相等，据我们观察，我们可以直接从主串的第五位开始与模式串进行比较，而事实上，却进行了几次多余的比较。使用nextval可以去除那些不必要的比较次数。　　求nextval数组值有两种方法，一种是不依赖next数组值直接用观察法求得，一种方法是根据next数组值进行推理，两种方法均可使用，视更喜欢哪种方法而定。　　我们使用例子“aaaab”来考查第一种方法。　　1.试想，在进行模式匹配的过程中，将模式串“aaaab”与主串进行匹配的时候，如果第一位就没有吻合，即第一位就不是a，那么不用比较了，赶快挪到主串的下一位继续与模式串的第一位进行比较吧，这时，模式串并没有发生偏移，那么，模式串第一位a的nextval值为0。　　2.如果在匹配过程中，到第二位才发生不匹配现象，那么主串的第一位必定是a，而第二位必定不为a，既然知道第二位一定不为a，那么主串的第一、二两位就没有再进行比较的必要，直接跳到第三位来与模式串的第一位进行比较吧，同样，模式串也没有发生偏移，第二位的nextval值仍然为0。　　3.第三位、第四位类似2的过程，均为0。　　4.如果在匹配过程中，直到第五位才发生不匹配现象，那么主串的第一位到第四位必定为a，并且第五位必定不为b，可是第五位仍然有可能等于a。如果万一第五位为a，那么既然前面四位均为a，所以，只要第六位为b，第一个字符串就匹配成功了。所以，现在的情况下，就是看第五位究竟是不是a了。所以发生了下面的比较：　　1 2 3 4 5 6　　a a a a * *　　a a a a b　　a a a a b　　前面的三个a都不需要进行比较，只要确定主串中不等于b的那个位是否为a，即可以进行如下的比较：如果为a，则继续比较主串后面一位是否为b；如果不为a，则此次比较结束，继续将模式串的第一位去与主串的下一位进行比较。由此看来，在模式串的第五位上，进行的比较偏移了4位（不进行偏移，直接比较下一位为0），故第五位b的nextval值为4。　　我们可以利用第一个例子“abaabcac”对这种方法进行验证。　　a的nextval值为0，因为如果主串的第一位不是a，那么没有再比较下去的必要，直接比较主串的第二位是否为a。如果比较到主串的第二位才发生错误，则主串第一位肯定为a，第二位肯定不为b，此时不能直接跳到第三位进行比较，因为第二位还可能是a，所以对主串的第二位再进行一次比较，偏移了1位，故模式串第二位的nextval值为1。以此类推，nextval值分别为：。其中第六位的nextval之所以为3，是因为，如果主串比较到第六位才发生不匹配现象，那么主串的前五位必定为“abaab”且第六位必定不是“c”，但第六位如果为“a”的话，那么我们就可以从模式串的第四位继续比较下去。所以，这次比较为： 1 2 3 4
5 6 7 8 9 10
12　　a b a a b * * * * * * *　　a b a a b c a c　　而不是： 1 2 3 4
5 6 7 8 9 10
12　　a b a a b * * * * * * *　　a b a a b c a　　因为前两位a和b已经确定了，所以不需要再进行比较了。所以模式串第六位的nextval值为这次比较的偏移量3。　　再来看求nextval数组值的第二种方法。　　模式串 a b a a b c a c　　next值 0 1 1 2 2 3 1 2　　nextval值 0 1 0 2 1 3 0 2　　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”内进行验证。 模式串 a a a a b　　next值 0 1 2 3 4　　nextval值 0 0 0 0 4
专注培养IT技术人才
主营：PHP培训，JAVA培训，HTML5培训，UI培训，Linux培训，Python培训
1条折叠回答
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。随手记录学习经历，有错误还望多多指正
Next 值与 Nextval 值的计算
KMP算法对模式串求解其Next值和Nextval值的计算方法
模式串S = “abaabcac” ，求其 Next 数值序列：
Next值的计算
Next值的计算，首先将串的字符进行标号，如下：
第一位的Next值为 0
第二位的Next值为 1
标准求解方法
第三位：前一位（第二位）的Next值为1 → 1对应的标号1的字符为a → （第二位）的字符b与标号1的字符a不同 → 但无法再找前一位匹配 → 所以第三位是 1
第四位：前一位（第三位）的Next值为1 → 对应标号字符为a → （第三位）的字符a与标号1的字符a相同 → 第四位Next值为第三位的Next值+1 = 2
第五位：前一位（第三位）的Next值为2 → 对应标号字符为b → （第四位）的字符a与标号2的字符b不同 → b的Next值为1 → 对应标号字符a → a与（第四位）字符相同 → 第五位Next 值为第二位**b**Next值1+1=2
第六位：前一位（第五位）的Next值为2 → 对应标号字符为b → （第五位）的字符b与标号2的字符b相同 → 第六位Next值为第五位的Next值+1 = 3
第七位：前一位（第六位）的Next值为3 → 对应标号字符为a → （第六位）的字符c与标号3的字符a不同 → a的Next值为1 → 对应标号字符a → a与（第四位）字符不同 → 但由于已经匹配到头 → 第七位的Next 值为1
第八位：前一位（第七位）的Next值为1 → 对应标号字符为a → （第七位）的字符a与标号1的字符a相同 → 第八位Next值为第七位的Next值+1 = 2
刷题时遇到的别人的解法，感觉很不错，记录一下
简述：Next 值就是字符串s的最长相同前缀和后缀子字符串的长度
首先前两位0、1 是固定不变的
- 第三位：字符串是”bab”，前缀有b, ba；后缀有ab,b，前后缀相等的最长字符串为b，长度为1，所以第三位Next值为1
- 第四位：字符串”baba”，前缀有b, ba, bab；后缀有aba, ba, a，前后缀相等的最长字符串为ba，长度为2，所以第三位Next值为2
- 第五位：字符串”babab”，前缀有b, ba, bab, baba；后缀有abab, bab, ab, b，前后缀相等的最长字符串为bab，长度为3，所以第三位Next值为3
注：经验证：使用方法二算出的S = “abaabcac”的Next值与使用方法一得到的值不同，所以方法二的正确性待确定
Nextval值的计算
Nextval是对Next的优化
**简述：**NextVal值就是字符串s的的最长相同且满足后续字符不同的前缀和后缀子字符串的长度。
上述字符串计数时时从1开始计数，那么从零开始的呢？
- 首先可以看到从 1 开始的，其 Next 值为：
- 然后从 0 开始的，Next 值为：
Nextval[i]
注意：可以看出，Next 值并不是第一个求得的值依次减一所对应的。
- Nextval[0] = -1 ，和Next[0]的值一样
- Nextval[1] ，Next[1] = 0 , s[0] = a ，a ≠ b（s[1]），则Nextval[1] = Next[1] = 0
- Nextval[2] ，Next[2] = 0 , s[0] = a ，a = a（s[2]），则Nextval[1] = Nextval[0] = -1
- Nextval[3] ，Next[3] = 1 , s[1] = b ，b = b（s[3]），则Nextval[3] = Nextval[1] = 0
- Nextval[4] ，Next[4] = 2 , s[2] = a ，a = a（s[4]），则Nextval[4] = Nextval[2] = 0
- Nextval[5] ，Next[5] = 3 , s[3] = b ，b ≠ a（s[5]），则Nextval[5] = Next[5] = 3
- Nextval[6] ，Next[6] = 1 , s[1] = b ，b = b（s[6]），则Nextval[6] = Nextval[1] = 0
- Nextval[7] ，Next[7] = 2 , s[2] = a ，a = a（s[7]），则Nextval[7] = Nextval[2] = -1
- Nextval[8] ，Next[8] = 3 , s[3] = b ，b = b（s[8]），则Nextval[8] = Nextval[3] = 0
没有更多推荐了，版权声明：本文为博主原创文章，未经博主允许，不得转载。
习题集解析部分
&&《数据结构题集》-严蔚敏.吴伟民版
& & & &源码使用说明&&链接???&
& & & &课本源码合辑&&链接???&
& & & &习题集全解析&&链接???&
& & & 相关测试数据下载 &链接?
& & & 本习题文档的存放目录：数据结构\▼配套习题解析\▼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的最左边的位置上出现）和所有的最长公共子串，讨论你的算法能否实现。
阅读(...) 评论()
版权声明：本文为博主原创文章，未经博主允许，不得转载。模式串的next函数值_中华文本库
求串的next函数值的方法 - 模式串‘aaaab’和‘adabbadada’ next和nextval数组值 记得大学时自己也总结出了这种算法的,手动计算,数据结构的书都丢了,还好在网上...
求串的next函数值的方法 - 模式串‘aaaab’和‘adabbadada’ next...... { //求模式串T的next函数修正值并存入数组nextval。 i=1; nextval[1]=0; j=0; ...
请用边界值分析法写出 NextDate 函数的测试用例 在 NextDate 函数中, 隐含规定了变量 mouth 和变量 day 的取值范围为 1≤mouth≤12 和 1≤day≤31 ,并设定...
其返回值-1,没有选中,0,没有定义,1,被选中 (2)有关下一个被选实体的取值函数 NDNEXT(N) ELNEXT(E) KPNEXT(K) LSNEXT(L) ARNEXT(A) VLNEXT(V) ...
2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 课堂练习-nextdate函数边界值分析 隐藏&& 课堂练习 ? NextDate...
3 4 5 6 C InputBox 函数返回的函数值的类型是(). 数值 字符串 数值或...Next m 答案 B 292 下列循环能正常结束循环的是 A) i=5 Do i=i+1 Loop...
强健壮 等价类测试中的无效测试用例可以包含多个无效值, 即含有多个缺陷假设。因为NextDate函数有三个变量, 所以对应的强健壮等价类测试用例可以包含一个无效 值,...
next,*q; int lena=1,j=0; while (p-&next!...4.1 采用顺序结构存储串,编写一个实现串通配符匹配的...(1)计算模式p的nextval函数值。 (2)不写算法,只...
试按上 述定义的结构改写求模式串的 next 函数值的算法。 注:根据同学们的要求,将作业量从六道题减少到三道题,希望同学们能及时完成。 第五章 数组和广义表 ...
用列表法求KMP算法中的next函数值 - 年第 期第卷总 吉林省教 育学 院学 报心笼人刊 甘住 肠 , 洲飞议 加 期 用 列表法 求 算法 中的 赵艳伟...}