前缀和的算法

A. 数据结构前缀后缀中缀算法

前缀：先写运算符，如a+b，写成+ab中缀：a+b写成a+b后缀：a+b写成ab+

B. 前缀函数

前缀 是指从串首开始到某个位置 结束的一个特殊子串。字符串 的以 结尾的前缀表示为
真前缀 指除了 本身的 的前缀。

后缀 是指从某个位置 开始到整个串末尾结束的一个特殊子串。字符串 的从 开头的后缀表示为
真后缀 指除了 本身的 的后缀。

给定一个长度为 的字符串 ，其 前缀函数 定义为一个长度为 的数组 。其中 含义为：

对于字符串 和 ，若 对于所有 成立，则称 是 的 周期 。

对于字符串 和 ，若 长度为 的前缀和长度为 的后缀相等，就称 长度为 的前缀（后缀）是 的 border 。

【注】易知前缀函数 对应的就是字符串 的最长 border 的长度。

根据前缀函数的定义我们可以发现，相邻的前缀函数值至多增加 1 ，故可以得到字符串 的前缀函数的计算公式：

【注】计算字符串的前缀函数的思想和 KMP 算法中计算字符串失配数组的思想非常相似。

前缀函数可以用来实现 KMP 算法，思路为：拼接模式串 和主串 ，得到 ， 为不在 和 中出现的字符。设 计算拼接后的字符串 的前缀函数，当出现 时，说明此时模式串匹配上了主串的子串 。

整个算法时间复杂度为 。

根据上文中给出的性质，可以很容易求出字符串 的字符串周期 & border。假设 ，则可以在 时间内求出 的所有周期 & border。

给定字符串 ，其长度 ，计算 中不同的子串的数目。

【注】从头部添加、头部移除或尾部移除后计算不同子串的思想类似。

根据上文的性质可知，如果计算出 的前缀函数之后， 的最小周期为 。由字符串的周期的定义可知，最后字符串 删去每段周期长度的字符串后，剩余的最后一段字符串长度不一定是 。故如果 ，则 即是 的长度，否则不存在一个有效的压缩，即 的长度为 。

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

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

D. 从最大连续和问题看算法的时间复杂度

参考紫书8.1章节。
最大连续和问题

在给定序列中找到最大连续和，该问题最简单的解答思路是将所有子序列的和求出，并找到最大值，但如果序列长度较大或序列中元素的值较大，计算需要的时间都将大幅增加。因此需要使用更优化的算法。以下列举四种算法，使用函数maxsum求出最大连续和，数组A存放给定序列，n表示序列长度。

求出所有子序列的和，逐个比较找出最大值，时间复杂度为n^3，当序列长度较长时，运算时间很可能超出要求。

使用前缀和将免去使用循环计算子序列和的部分，因此时间复杂度减少到n^2，但在n过大时仍然需要较多时间。

将序列划分为左右两个区间，并利用递归求出左区间，右区间的最大值，利用循环求出合并区间的最大值，最终比较得出结果。对这一题目使用分治法时maxsum函数使用了递归和一重循环，最终时间复杂度为nlogn，时间复杂度随n的增加而增加的幅度更小了。

同样使用前缀和计算子序列的和，在前面的解法中，子序列的和=S[j]-S[i-1]，只要将最小的S[i-1]记录下来，就可以直接用S[j]减去最小的S[i-1]，得到子序列的最大和，于是又省略了一种循环，时间复杂度被降到n。

若题目范围中n的可取值较大，我们就不太可能使用前几种时间复杂度的程序解答，若n的取值较小，则可以使用。

E. 指出BM算法与KMP算法的区别

KMP算法和BM算法，它们分别是前缀匹配和后缀匹配的经典算法。
1、因为路由表中的每个表项都指定了一个网络，所以一个目的地址可能与多个表项匹配。最明确的一个表项，即子网掩码最长的一个，就叫做最长前缀匹配。
2、之所以这样称呼它，是因为这个表项也是路由表中，与目的地址的高位匹配得最多的表项。

F. 增1减1运算符，前缀运算和后缀运算请大大们详细举例讲解，为什么有变量的值和表达式的值

额
举个例子

下面的几个表达式都在 int i=0 的基础上运算
1：int j = i++；这里i=0、表达式的值j=1；
2：int j = ++i；这里i=1、表达式的值j=1；
3：int j = i--；这里i=0、表达式的值j=-1；
4：int j = --i；这里i=-1、表达式的值j=-1；

这4个例子你应该能明白一点吧
其实就是两个重点
1：前缀会在表达式运算前获得新值、后缀在表达式运算后获得新值
2：表达式和变量的值是两个概念，要注意分离

G. Java 前缀和算法 谢谢

算法太多了

H. 这个为什么前缀和后缀算法都等于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

I. C语言创建动态数组，计算前缀和数组。 b是数组a的前缀和的数组定义：b[i]=a[0]+a[1]

关于在 C 语言中创建动态数组的问题，可以使用 C 语言提供的库函数：malloc( ) 来创建动态数组。即可以使用如下代码进行实现：
#include <stdlib.h> /* 动态分配内存的库函数 malloc( )、以及后面用到的 free( ) 释放内存库函数在此头文件中有函数原型定义，故必须包含该头文件 */
#include <stdio.h>
void main( )
{
int num, * p ;

printf("Please input a number :\n" ) ;

scanf("%d", &num) ;

p = (int *)malloc(num) * sizeof(int) ; /* 根据前面从键盘上输入的数字 num，动态分配一个整型动态数组 p */

......
......
free( p ) ; /* 应用程序结束前务必释放内存 */

}
至于说中间的程序结构的架构，就需要靠自己上机编写、并亲自调试程序了。因为任何一个程序的最终正确运行结果（可以说是100%的程序），都是必须在编程环境下面调试出来的，而不是在纸上写出来就能够保证通过的。
在纸上写出来的部分源代码，只能够是给你提供一个大致的编程思路供参考。