nextval

关于KMP算法中的nextval【】数组是怎么得到的？

KMP 算法我们有写好的函数帮我们计算 Next 数组的值和 Nextval 数组的值，但是如果是考试，那就只能自己来手算这两个数组了，这里分享一下我的计算方法吧。

计算前缀 Next[i] 的值:

我们令 next[0] = -1 。从 next[1] 开始，每求一个字符的 next 值，就看它前面是否有一个最长的"字符串"和从第一个字符开始的"字符串"相等(需要注意的是，这2个"字符串"不能是同一个"字符串")。如果一个都没有，这个字符的 next 值就是0；如果有，就看它有多长，这个字符的 next 值就是它的长度。

计算修正后的 Nextval[i] 值:

我们令 nextval[0] = -1。从 nextval[1] 开始，如果某位(字符)与它 next 值指向的位(字符)相同，则该位的 nextval 值就是指向位的 nextval 值(nextvalue[i] = next[ next[i] ])；如果不同，则该位的 nextval 值就是它自己的 next 值(nextvalue[i] = next[i])。

举个例子:



计算前缀 Next[i] 的值:

next[0] = -1;定值。
next[1] = 0;s[1]前面没有重复子串。
next[2] = 0;s[2]前面没有重复子串。
next[3] = 0;s[3]前面没有重复子串。
next[4] = 1;s[4]前面有重复子串s[0] = 'a'和s[3] = 'a'。
next[5] = 2;s[5]前面有重复子串s[01] = 'ab'和s[34] = 'ab'。
next[6] = 3;s[6]前面有重复子串s[012] = 'abc'和s[345] = 'abc'。
next[7] = 4;s[7]前面有重复子串s[0123] = 'abca'和s[3456] = 'abca'。

计算修正后的 Nextval[i] 值:

nextval[0] = -1;定值。
nextval[1] = 0;s[1] != s[0]，nextval[1] = next[1] = 0。
nextval[2] = 0;s[2] != s[0]，nextval[2] = next[2] = 0。
nextval[3] = -1;s[3] == s[0]，nextval[3] = next[0] = -1。
nextval[4] = 0;s[4] == s[1]，nextval[4] = next[1] = 0。
nextval[5] = 0;s[5] == s[2]，nextval[5] = next[2] = 0。
nextval[6] = -1;s[6] == s[3]，nextval[6] = next[3] = -1。
nextval[7] = 4;s[7] != s[4]，nextval[7] = next[7] = 4。

求模式串‘aaaab’和‘adabbadada’ next和nextval数组值

　　尊敬的玩家：
　　您好：


　　模式串‘aaaab’和‘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值分别为：01021302。其中第六位的nextval之所以为3，是因为，如果主串比较到第六位才发生不匹配现象，那么主串的前五位必定为“abaab”且第六位必定不是“c”，但第六位如果为“a”的话，那么我们就可以从模式串的第四位继续比较下去。所以，这次比较为： 1 2 3 4 5 6 7 8 9 10 11 12
　　a b a a b * * * * * * *
　　a b a a b c a c

　　而不是： 1 2 3 4 5 6 7 8 9 10 11 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


　　百度知道专家，《梦幻西游干将》团队团长为你服务
　　如果还有什么疑问，请继续提问
　　在我们的共同努力下，“知道”一定能成为充满温馨和智慧的知识社区

编程语言一共有多少种？

编程语言的种类繁多，总的来说分为机器语言、汇编语言以及高级语言三大类。机械语言（machine language）：计算机可直接识别、运行的二进制代码，执行速度快，资源占用少，但可读性不强，编程复杂；汇编语言（assembly language）：一种用于电子计算机、微处理器、微控制器或其他可编程器件的低级语言，亦称为符号语言。目标代码简短，占用内存少，执行速度快，但缺乏可移植性，编程复杂；高级语言（High-level programming language）：相对于机器语言以及汇编语言，高级语言的可读性强，可移植性高，一般通过事先编好的一个叫做编译程序的机器语言程序编译成用机器指令表示的目标程序。现在流行的高级语言有Java、C语言、C++、C#、Pascal、Basic等等。

一般游戏编程用什么语言和软件

下面是游戏开发十大编程语言的列表。1、C类＃C语言现在被广泛应用于许多游戏引擎中，是最流行的游戏开发语言之一。它有一个XNA框架、一套微软工具和运行时环境，使它特别适合Xbox或windows上的游戏。如果你想使用monogame在几乎任何平台上发布游戏，这是一种很好的语言。2、C类＋＋C＋＋是一种面向对象的语言，被认为是最难学习的语言之一，但它是游戏开发人员的重要语言。它允许对硬件和图形进程进行更直接的控制，这对行业很重要，是一些流行游戏引擎的流行语言。它还提供了对参数和内存管理的大量控制，从而提高了游戏的性能和用户体验。3、JavaJava使用与C＋＋相同的面向对象原则，但提供了更广泛的系统。Java代码通常在Java虚拟机（JVM）上运行，并转换为可在任何系统上执行的通用字节码。因此，Java是为数不多的能够让开发人员为任何给定系统开发游戏的游戏编程语言之一。它是最好的游戏编程语言之一。4、JavaScriptJavaScript是最流行的游戏编程语言之一，尤其是作为一种在线交互语言。使用JavaScript，可以更容易地将代码与传统的网络技术（如HTML和CSS）集成，从而导致越来越多的跨平台移动游戏。5、HTML5HTML5已经成为互联网上最常见的游戏编程语言之一。你今天玩的大多数手机游戏都使用这种标记语言。使用JavaScript很容易创建复杂的基于web的游戏。该语言简单易学，不一定需要学习复杂的算法编程知识，因此成为游戏开发者的热门选择。6、SQL语言SQL被玩家用来访问后端帐户并在服务器上执行其他操作。有新的语言，库，框架，特别是AR，VR，图形，物理和游戏。7、PythonPython是另一种提供OOP方法的语言，是游戏开发人员使用的最易于使用的通用编程语言之一。它有一个pyGame框架，允许程序员快速开发游戏原型。8、Rust铁锈被吹捧为C的继承者之一。它主要被Mozilla基金会用作系统编程语言。它具有面向对象到面向数据的方法，有助于游戏开发。9、UnrealScriptUnrealscript是unreal引擎的本机脚本语言。它结合了面向对象、多重继承和功能丰富的游戏等复杂功能。该语言支持所有主要的游戏平台，如微软Windows、MacOS、Linux、steamos、Android和PlaystationVR。10、Lua由于语言结构和语法简单，Lua正成为游戏界最流行的语言之一。它是一种多平台脚本语言，许多现代游戏引擎都使用Lua作为主要的游戏设计编程语言。