前缀和算法

❶ 这个为什么前缀和后缀算法都等于8 具体怎么算的

前缀运算：
÷+*+1*2 4 5 3*1 6
=÷+*+1*2 4 5 3 6
=÷+*+1 8 5 3 6
=÷+*9 5 3 6
=÷+45 3 6
=÷48 6
=8

后缀运算：
1 2 4 *+5*3+1 6*÷
=1 8+5*3+1 6*÷
=9 5*3+1 6*÷
=45 3+1 6*÷
=48 1 6*÷
=48 6÷
=8

❷ 密码机前缀为什么是SJ

首先对于非对称加密体制，对RSA算法作了详细的说明，RSA算法基于大数模幂乘运算，其运行效率决定了RSA非对称密码的性能，文中说明了各种模幂算法的快速实现方法，并进行比较分析。

其次对于对称加密体制，以DES（Data Encryption Standard，数据加密标准）算法和Rijndael算法为重点，首先对DES和Rijndael算法的加密原理进行说明，并通过对算法的分析找出它们的不足之处，如DES算法，易受选择明文法攻击，而Square攻击法是对Rijndael算法最有效的攻击法。

它们的攻击原理是基于加密系统的不变性，因此本文提出了基于前缀码的解决方案，因为前缀码具有很好的译码特性，通过前缀码的引入可以对输入的明文译码，以此来改变算法子密钥的使用顺序，从而使加密系统不再固定不变，而是随着明文的不同而不断变化，使算法对攻击具有很好的抵抗性。

最后对数字签名过程进行分析，由于MD5算法已经被破解，所以数字签名存在着被伪造的隐患。

因此本文提出了基于前缀码的数字签名改进方案，通过前缀码的译码特性对MD5算法产生的摘要进行译码、变换，然后再通过网络传输，消除了数字签名可能被伪造的隐患。

❸ kmp求next数组

KMP算法，主要分为2个阶段：

• 求next数组。
  

• 字符串匹配

• next数组，就是对给定的“匹配字符串”，求出其每一个子长度字串的“最长前缀和最长后缀相等的长度”。

匹配串，p="aabcaabbaa", 长度n=10。因此子串为sub[10]：



sub[0]="a"sub[1]="aa"sub[2]="aab"sub[3]="aabc"sub[4]="aabca"sub[5]="aabcaa"sub[6]="aabcaab"sub[7]="aabcaabb"sub[8]="aabcaabba"sub[9]="aabcaabbaa"


根据“最长前缀和最长后缀相等的长度”，可以求出对应的next数组是：




next[0]=-1;//"a"next[1]=0;//"aa"next[2]=-1;//"aab"next[3]=-1;//"aabc"next[4]=0;//"aabca"next[5]=1;//"aabcaa"next[6]=-1;//"aabcaab"next[7]=-1;//"aabcaabb"next[8]=0;//"aabcaabba"next[9]=1;//"aabcaabbaa"

2. 利用上部求出的next数组，对t和p进行匹配。要点是：



（1）循环匹配（2）如果整个匹配上，则返回匹配位置。（3）如果当前位置没有匹配上，则：如果对应next[x]为-1，则跳过整个p的长度；否则，回溯到其前缀位置进行匹配。匹配上，则右移next[x-1]位置；否则，右移next[x]位置。

具体到“多少次字符匹配”，在编制的程序里加上统计的语句，最后输出。真要一个个字符统计，很容易出错。

❹ 算法-KMP

大一下参加学校ACM预备队集训的时候首次接触KMP算法，当时看了很多介绍文章，仍然不是很理解其实质，只是简单地套模板AC题目，待大二数据结构与算法课堂上再听老师介绍一次，才恍然大悟其实KMP也就是那么回事嘛。但当初为啥看那么多文章都没弄明白呢？正巧最近和朋友聊天时他告诉我他对KMP不是很理解，于是打算自己写一篇文章，巩固自己对KMP的认识，也希望能够帮助更多朋友理解KMP。
在开始之前，需要知晓的概念：

前缀：以原串串头为自身串头的子串，如 的前缀有：
后缀：以原串串尾为自身串尾的子串，如 的后缀有：

注意：字符串前后缀都不包括该串本身

给你一个文本串T(Text String)

再给你一个模式串P(Pattern String)

问该模式串是否在文本串中，怎么找？

一开始只好分别从文本串与模式串的串头开始逐字母比较

二者相同，再比较T串与P串的下一位

如此反复

如果一直这么顺利，两串对应位置的字符总相同，待P串中最后一个字符也匹配完毕，说明该模式串在文本串中存在，耶( •̀ ω •́ )y超开心，查找结束。但，大多数匹配过程不会如此顺利，在该例中，当匹配进行至

很明显，失配了。现在怎么办？按朴素思想，将P串相对T串整体右移一位，重新开始匹配，即

但这种算法效率无疑是十分低下的。设T串长度N，P串长度M，则朴素算法时间复杂度为O(MN)

已知的重要信息并没有被使用——已匹配的字符串前缀

在上例中，当P串最后一个字符匹配失败时，其已有包含七个字符的 前缀子串S 匹配成功

完全可以利用前缀子串S做点什么。观察到在S串

中，有相同前后缀，即下图蓝色部分

而S串各字符又与T串中对应字符相同，即有

当失配发生后，直接将P串右移四位使S串蓝色后缀部分对齐T串中蓝色前缀部分

从图中红框部分继续尝试匹配，发现再次失配。这次，已匹配成功的前缀串S为

而在该串中没有相同的前后缀，只能将P串串头移至失配处进行比较

再次失配。此时前缀串S为空串，只好如朴素算法般将P串整体右移一位，重新开始比较

匹配成功。于是又按照之前的步骤往下匹配，直至再次失配或匹配成功

后续步骤同上，不再赘述

上述示例已展现，KMP算法的精髓在于对已匹配成功的前缀串S的利用

在朴素算法中，匹配失败了，T串待匹配字符会回溯

T串原本已匹配至T[7] = 'X'，但是因为失配，需回溯到T[1] = 'b'重新开始匹配

而在KMP算法中，若P[M]与T[K]匹配失败，K不会回溯。既然匹配过程是从T[0]开始逐渐向右进行的，至T[K]失配发生时，T[0]至T[K-1]早已匹配过，何必再回溯过去重复匹配呢？于是乎，就如问题引入部分展示般

每当失配发生，我们总是去关注P串中已匹配成功的前缀串S

因为该前缀串是匹配成功的，说明在T串中必定存在与该前缀串相同的子串，记为S'

若S串中存在相同前后缀

则S'串必然也存在此相同前后缀

所以只需将P串右移四位，使得S串的该相同前缀对齐S'串的该相同后缀

再尝试比较T[7]与P[3]

至于T[7]与P[3]是否能够匹配另说（当然，本例中一看就知道没匹配上），但通过对前缀串S的利用，成功省去了P串右移一位、两位和三位后的无效匹配

继续深入思考，给定一个具体的P串，其第N位的前缀串S内容是固定的，则S是否存在相同前后缀、相同前后缀的长度与内容也是确定的。换言之，对于一个具体的P串，当其与给定T串匹配至P[N]失配，P串应右移几位再次与T串进行匹配也是确定的。我们完全可以使用一个数组记录当P[N]失配后，应当使用N之前的哪一位再来与T串进行匹配，以此提高匹配效率，记该数组为Next数组

定义Next[i] = j表示当P串中第i位失配后，跳转至P串第j位再次尝试匹配

还是以之前的P串为例，它的Next数组求出来应为

取下标5为例，其前缀串为

最长相同前后缀为

若P[5]失配，应跳转至P[1]再次尝试匹配（最长相同前缀对应P[0]，则取其后一位P[1]，若存在多位，则取最后一位的下一位），P[5]的前一个字符P[4]对应字符'a'，而P[1]前一个字符P[0]同对应字符'a'，保证了P[1]之前字符与T串中对应字符保持匹配。所以Next[5] = 1，其余下标对应Next数组值同如此求。

特别地，规定Next[0] = -1。而对于除下标0外的任意下标N，Next[N]的含义是 前N-1个已匹配成功的字符构成的前缀串S中，最长相同前后缀长度。 所以若在下标为N处匹配失败了，则应前往Next[N]所对应的下标处匹配。

具体地，以下图所示为例，P[6]与T[6]失配

而Next[6] = 2，所以使用P[2]再次尝试与T[6]进行匹配

当求出P串Next数组后，便可快速进行与T串的匹配

现在问题只剩下如何求Next数组，注意到Next数组既然只与P串本身相关，与文本串T无关，故令P串与自身匹配即可求得

考虑字符串

其Next数组应为

令其与给定文本串相匹配

当匹配进行至

失配，于是跳转至P[Next[3]] = P[1]处再次尝试匹配

再度失配，也必然失配

问题在于不该出现P[N] =P[Next[N]]

若P[N] =P[Next[N]]，则P[N]失配后使用P[Next[N]]再次尝试匹配，由于P[N] =P[Next[N]]，P[N]匹配失败，P[Next[N]]必然也失败

因此，若出现P[N] =P[Next[N]]情况，则令Next[N]=Next[Next[N]]

本例中该字符串新Next数组为

当匹配进行至

失配，于是跳转至P[Next[3]] = P[0]处再次尝试匹配

省去了之前跳转至P[1]处的无效匹配

设T串长度M，P串长度N，由于KMP算法不会回溯，分析易知时间复杂度为O(m+n)

对于P[N]，若其前缀串S含相同前后缀F，且F长度为n（n>1），Next[N]可以取1至n中任意值，为最大化匹配效率考虑，总是取最大相同前后缀以提高效率，节省时间

❺ 前缀、中缀、后缀表达式怎么画成二叉树（不要算法，不要代码，写出怎么画就行）

先说二叉树：
这里的前中后指的根的顺序，前的顺序是：根左右
中的顺序是：左根右
后的顺序是：左右根
比如有树的前序为：ABDHIECFG
中序为：HDIBEACFG
可以画出整棵树
你这里想画出一棵二叉树，那么你可以算出他的前缀，中缀可以确定一棵树，中缀，后缀也可以，前缀，后缀不可以确定一棵树，单纯的前缀，中缀，后缀不可以确定一棵树
（我也不太确定你的问题问的是什么）

❻ 图解KMP字符串匹配算法

kmp算法跟之前讲的bm算法思想有一定的相似性。之前提到过，bm算法中有个好后缀的概念，而在kmp中有个好前缀的概念，什么是好前缀，我们先来看下面这个例子。

观察上面这个例子，已经匹配的abcde称为好前缀，a与之后的bcde都不匹配，所以没有必要再比一次，直接滑动到e之后即可。
  那如果前缀中有互相匹配的字符呢？

观察上面这个例子，这个时候如果我们直接滑到好前缀之后，则会过度滑动，错失匹配子串。那我们如何根据好前缀来进行合理滑动？

  其实就是看当前的好前缀的前缀和后缀是否有匹配的，找到最长匹配长度，直接滑动。鉴于不止一次找最长匹配长度，我们完全可以先初始化一个数组，保存在当前好前缀情况下，最长匹配长度是多少，这时候我们的next数组就出来了。

  我们定义一个next数组，表示在当前好前缀下，好前缀的前缀和后缀的最长匹配子串长度，这个最长匹配长度表示这个子串之前已经匹配过匹配了，不需要再次进行匹配，直接从子串的下一个字符开始匹配。

 我们是否每次算next[i]时都需要每一个字符进行匹配，是否可以根据next[i - 1]进行推导以便减少不必要的比较。
  带着这个思路我们来看看下面的步骤：
  假设next[i - 1] = k - 1;
  如果modelStr[k] = modelStr[i] 则next[i]=k

如果modelStr[k] != modelStr[i]，我们是否可以直接认定next[i] = next[i - 1]？

通过上面这个例子，我们可以很清晰地看到，next[i]!=next[i-1]，那当modelStr[k]!=modelStr[i]时候，我们已知next[0],next[1]…next[i-1]，如何推导出next[i]呢？
  假设modelStr[x…i]是前缀后缀能匹配的最长后缀子串，那么最长匹配前缀子串为modelStr[0…i-x]

我们在求这个最长匹配串的时候，他的前面的次长匹配串（不包含当前i的），也就是modelStr[x…i-1]在之前应该是已经求解出来了的，因此我们只需要找到这个某一个已经求解的匹配串，假设前缀子串为modelStr[0…i-x-1],后缀子串为modelStr[x…i-1],且modelStr[i-x] == modelStr[i],这个前缀后缀子串即为次前缀子串，加上当前字符即为最长匹配前缀后缀子串。
代码实现
  首先在kmp算法中最主要的next数组，这个数组标志着截止到当前下标的最长前缀后缀匹配子串字符个数，kmp算法里面，如果某个前缀是好前缀，即与模式串前缀匹配，我们就可以利用一定的技巧不止向前滑动一个字符，具体看前面的讲解。我们提前不知道哪些是好前缀，并且匹配过程不止一次，因此我们在最开始调用一个初始化方法，初始化next数组。
  1.如果上一个字符的最长前缀子串的下一个字符==当前字符，上一个字符的最长前缀子串直接加上当前字符即可
  2.如果不等于，需要找到之前存在的最长前缀子串的下一个字符等于当前子串的，然后设置当前字符子串的最长前缀后缀子串

然后开始利用next数组进行匹配，从第一个字符开始匹配进行匹配，找到第一个不匹配的字符，这时候之前的都是匹配的，接下来先判断是否已经是完全匹配，是直接返回，不是，判断是否第一个就不匹配，是直接往后面匹配。如果有好前缀，这时候就利用到了next数组，通过next数组知道当前可以从哪个开始匹配，之前的都不用进行匹配。

❼ 网络前缀长度怎么计算麻烦写一下有哪些数字计算

你把IP和掩码全部换算成二进制，IP中和掩码中全1的位对应的就是网络号（网络前缀）
没什么算法的

❽ 请教波兰表达式前缀表达式的算法

对于一个前缀表达式的求值而言，首先要从右至左扫描表达式，从右边第一个字符开始判断，如果当前字符是数字则一直到数字串的末尾再记录下来，如果是运算符，则将右边离得最近的两个“数字串”作相应的运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时，最后运算的值也就是表达式的值。例如，前缀表达式“- 1 + 2 3“的求值，扫描到3时，记录下这个数字串，扫描到2时，记录下这个数字串，当扫描到+时，将+右移做相邻两数字串的运算符，记为2+3，结果为5，记录下这个新数字串，并继续向左扫描，扫描到1时，记录下这个数字串，扫描到-时，将-右移做相邻两数字串的运算符，记为1-5，结果为-4，所以表达式的值为-4。

❾ 前缀中缀后缀表达式的转换，能帮一下吗

思路的话其实很简单，就是构建一棵二叉树，根节点和中间节点为运算符，叶子结点为运算数字。如 a + b*c， 构建为二叉树的话，就如下图： +a * b c对于该二叉树，使用不同的遍历方式就可以得到不同的表达式了。遍历的代码很简单就不多说了。因此，你的问题主要可以分解为3个小问题：1。将后缀表达式转换为二叉树 该方法是最简单的。如a + b*c 的后缀表达式为 bc*a+.处理步骤如下： 1。建立一个栈S
2。从左到右读后缀表达式，读到数字就创建叶子节点，节点值为数字值。将节点压入栈S中，读到运算符则创建中间节点，并从栈中依次弹出两个节点分别为Y和X，作为中间节点的左右子节点，然后以“X 运算符 Y”的形式计算机出中间节点的值，再将此中间节点压加栈S中 3。就重复第二步直至后缀表达式结束，此时栈顶的节点就是二叉树的根节点了。2。将中缀表达式转换为二叉树 按照上一个回答者的方法将中缀表达式转为后缀表达式，然后调用后缀表达式生成二叉树的解法即可。3。将前缀表达式转换为二叉树 将前缀表达式直接取反即为后缀表达式。 如前缀表达式为+*bca，对应的后缀表达式为acb*+。因此，我们只需要字符串取反，然后调用后缀表达式的方法生成二叉树即可。