再谈最长公共子串问题

算法常用术语中英对照Data Structures 基本数据结构Dictionaries 字典Priority Queues 堆Graph Data Structures 图Set Data Structures 集合Kd-Trees 线段树Numerical Problems 数值问题Solving Linear Equations 线性方程组Bandwidth Reduction 带宽压缩Matrix Multiplication 矩阵乘法Determinants and Permanents 行列式Constrained and Unconstrained Optimization 最值问题Linear Programming 线性规划Random Number Generation 随机数生成Factoring and Primality Testing 因子分解/质数判定Arbitrary Precision Arithmetic 高精度计算Knapsack Problem 背包问题Discrete Fourier Transform 离散Fourier变换Combinatorial Problems 组合问题Sorting 排序Searching 查找Median and Selection 中位数Generating Permutations 排列生成Generating Subsets 子集生成Generating Partitions 划分生成Generating Graphs 图的生成Calendrical Calculations 日期Job Scheduling 工程安排Satisfiability 可满足性Graph Problems -- polynomial 图论-多项式算法Connected Components 连通分支Topological Sorting 拓扑排序Minimum Spanning Tree 最小生成树Shortest Path 最短路径Transitive Closure and Reduction 传递闭包Matching 匹配Eulerian Cycle / Chinese Postman Euler回路/中国邮路Edge and Vertex Connectivity 割边/割点Network Flow 网络流Drawing Graphs Nicely 图的描绘Drawing Trees 树的描绘Planarity Detection and Embedding 平面性检测和嵌入Graph Problems -- hard 图论-NP问题Clique 最大团Independent Set 独立集Vertex Cover 点覆盖Traveling Salesman Problem 旅行商问题Hamiltonian Cycle Hamilton回路Graph Partition 图的划分Vertex Coloring 点染色Edge Coloring 边染色Graph Isomorphism 同构Steiner Tree Steiner树Feedback Edge/Vertex Set 最大无环子图Computational Geometry 计算几何Convex Hull 凸包Triangulation 三角剖分Voronoi Diagrams Voronoi图Nearest Neighbor Search 最近点对查询Range Search 围查询Point Location 位置查询Intersection Detection 碰撞测试Bin Packing 装箱问题Medial-Axis Transformation 中轴变换Polygon Partitioning 多边形分割Simplifying Polygons 多边形化简Shape Similarity 相似多边形Motion Planning 运动规划Maintaining Line Arrangements 平面分割Minkowski Sum Minkowski和Set and String Problems 集合与串的问题Set Cover 集合覆盖Set Packing 集合配置String Matching 模式匹配Approximate String Matching 模糊匹配Text Compression 压缩Cryptography 密码Finite State Machine Minimization 有穷自动机简化Longest Common Substring 最长公共子串Shortest Common Superstring 最短公共父串robustness 鲁棒性rate of convergence 收敛速度********************************************************************* 数据结构基本英语词汇数据抽象data abstraction数据元素data element数据对象data object数据项data item数据类型data type抽象数据类型abstract data type逻辑结构logical structure物理结构phyical structure线性结构linear structure非线性结构nonlinear structure基本数据类型atomic data type固定聚合数据类型fixed-aggregate data type 可变聚合数据类型variable-aggregate data type 线性表linear list栈stack队列queue串string数组array树tree图grabh查找，线索searching更新updating排序（分类) sorting插入insertion删除deletion前趋predecessor后继successor直接前趋immediate predecessor直接后继immediate successor双端列表deque(double-ended queue) 循环队列cirular queue指针pointer先进先出表（队列）first-in first-out list 后进先出表（队列）last-in first-out list 栈底bottom栈定top压入push弹出pop队头front队尾rear上溢overflow下溢underflow数组array矩阵matrix多维数组multi-dimentional array以行为主的顺序分配row major order 以列为主的顺序分配column major order 三角矩阵truangular matrix对称矩阵symmetric matrix稀疏矩阵sparse matrix转置矩阵transposed matrix链表linked list线性链表linear linked list单链表single linked list多重链表multilinked list循环链表circular linked list双向链表doubly linked list十字链表orthogonal list广义表generalized list链link指针域pointer field链域link field头结点head node头指针head pointer尾指针tail pointer串string空白（空格）串blank string空串（零串）null string子串substring树tree子树subtree森林forest根root叶子leaf结点node深度depth层次level双亲parents孩子children兄弟brother祖先ancestor子descentdant二叉树binary tree平衡二叉树banlanced binary tree 满二叉树full binary tree完全二叉树complete binary tree遍历二叉树traversing binary tree 二叉排序树binary sort tree二叉查找树binary search tree线索二叉树threaded binary tree 哈夫曼树Huffman tree有序数ordered tree无序数unordered tree判定树decision tree双链树doubly linked tree数字查找树digital search tree树的遍历traversal of tree先序遍历preorder traversal中序遍历inorder traversal后序遍历postorder traversal图graph子图subgraph有向图digraph(directed graph)无向图undigraph(undirected graph) 完全图complete graph连通图connected graph非连通图unconnected graph强连通图strongly connected graph 弱连通图weakly connected graph 加权图weighted graph有向无环图directed acyclic graph 稀疏图spares graph稠密图dense graph重连通图biconnected graph二部图bipartite graph边edge顶点vertex弧arc路径path回路（环）cycle弧头head弧尾tail源点source终点destination汇点sink权weight连接点articulation point初始结点initial node终端结点terminal node相邻边adjacent edge相邻顶点adjacent vertex关联边incident edge入度indegree出度outdegree最短路径shortest path有序对ordered pair无序对unordered pair简单路径simple path简单回路simple cycle连通分量connected component邻接矩阵adjacency matrix邻接表adjacency list邻接多重表adjacency multilist遍历图traversing graph生成树spanning tree最小（代价）生成树minimum(cost)spanning tree 生成森林spanning forest拓扑排序topological sort偏序partical order拓扑有序topological orderAOV网activity on vertex networkAOE网activity on edge network关键路径critical path匹配matching最大匹配maximum matching增广路径augmenting path增广路径图augmenting path graph查找searching线性查找（顺序查找）linear search (sequential search) 二分查找binary search分块查找block search散列查找hash search平均查找长度average search length散列表hash table散列函数hash funticion直接定址法immediately allocating method数字分析法digital analysis method平方取中法mid-square method折叠法folding method除法division method随机数法random number method排序sort部排序internal sort外部排序external sort插入排序insertion sort随小增量排序diminishing increment sort选择排序selection sort堆排序heap sort快速排序quick sort归并排序merge sort基数排序radix sort外部排序external sort平衡归并排序balance merging sort二路平衡归并排序balance two-way merging sort 多步归并排序ployphase merging sort置换选择排序replacement selection sort文件file主文件master file顺序文件sequential file索引文件indexed file索引顺序文件indexed sequential file索引非顺序文件indexed non-sequential file直接存取文件direct access file多重链表文件multilist file 倒排文件inverted file目录结构directory structure 树型索引tree index。

OI笔记]后缀数组学习笔记--后缀数组解题方法总结2010-04-15 07:37后缀数组是处理字符串的有力工具。

后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也并不逊色，而且它比后缀树所占用的内存空间小很多。

可以说，后缀数组比后缀树要更为实用。

自从拜读了罗穗骞大牛的WC2009论文《后缀数组——处理字符串的有力工具》后，经过若干星期的努力（中间有因某些原因而缓下来），终于把论文上面的练习题全部完成了，现在写写自己对后缀数组的理解和感悟。

在看本笔记时，请不要忘记了，这是笔记，而教材是《后缀数组——处理字符串的有力工具》。

一：后缀数组的实现1、定义：Suffix Array数组（SA数组）用于保存从小到大排好序之后的后缀。

RANK名次数组用来保存后缀S[i..n]在所有后缀中是第几小的后缀。

简单来说，SA数组表示的是“排第几的是谁”，RANK数组表示的是“你的排名是多少”。

2、求SA数组以及RANK数组的方法：详细的请转到罗穗骞大牛的论文，我的学习笔记重点不是要介绍这个。

3、对DA（倍增算法）的一些个人理解：由于我只学习了倍增算法，所以我只能谈谈我对它的理解。

DC3算法我没有去研究....DA算法我是根据罗穗骞的模板写的，根据自己的理解做了些许的小优化。

我们现在来看看罗穗骞大牛的模板：int wa[maxn],wb[maxn],wv[maxn],ws[maxn];int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}void da(int *r,int *sa,int n,int m){int i,j,p,*x=wa,*y=wb,*t;for(i=0;i<m;i++) ws[i]=0;for(i=0;i<n;i++) ws[x[i]=r[i]]++;for(i=1;i<m;i++) ws[i]+=ws[i-1];for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;for(j=1,p=1;p<n;j*=2,m=p){for(p=0,i=n-j;i<n;i++) y[p++]=i;for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;for(i=0;i<n;i++) wv[i]=x[y[i]];for(i=0;i<m;i++) ws[i]=0;for(i=0;i<n;i++) ws[wv[i]]++;for(i=1;i<m;i++) ws[i]+=ws[i-1];for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}return;}其实，我个人认为，对于这个算法以及代码，无需过分深入地理解，只需记忆即可，理解只是为了帮助记忆罢了。

ACM 题型算法分类题目均来自：/JudgeOnline/主流算法：1.搜索//回溯2.DP（动态规划）3.贪心4.图论//Dijkstra、最小生成树、网络流5.数论//解模线性方程6.计算几何//凸壳、同等安置矩形的并的面积与周长7.组合数学//Polya定理8.模拟9.数据结构//并查集、堆10.博弈论1、排序1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380,1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379,1002（需要字符处理，排序用快排即可） 1007（稳定的排序） 2159（题意较难懂） 2231 2371（简单排序） 2388（顺序统计算法） 2418（二叉排序树）2、搜索、回溯、遍历1022 1111d 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 2386 1010,1011,1018,1020,1054,1062,1256,1321,1363,1501，1650,1659,1664,1753,2078,2083,2303,2310,2329简单：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742,1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426,不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197,2349,推荐：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709,1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170,2288, 2331, 2339, 2340,1979（和迷宫类似） 1980（对剪枝要求较高）3、历法1008 2080 （这种题要小心）4、枚举1012，1046， 1387， 1411， 2245， 2326， 2363， 2381，1054（剪枝要求较高），1650 （小数的精度问题）5、数据结构的典型算法容易：1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395, 不易：1145, 1177, 1195, 1227, 1661, 1834,推荐：1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010,2119, 2274, 1125(弗洛伊德算法) ，2421（图的最小生成树）6、动态规划1037 A decorative fence、1050 To the Max、1088 滑雪、1125 Stockbroker Grapevine、1141 Brackets Sequence、1159 Palindrome、1160 Post Office、1163 The Triangle、1458 Common Subsequence、1579 Function Run Fun、1887 Testing the CATCHER、1953 World Cup Noise、2386 Lake Counting7、贪心1042, 1065, 1230, 1323, 1477, 1716, 1784,1328 1755（或用单纯形方法），2054，1017， 1328，1862， 1922 ，2054， 2209， 2313， 2325， 2370。

第四章串作业参考答案：1、简述空串和空格串（或称空格符串）的区别1）空串是指不包括任何字符的串，空格串指包含若干个空格字符的字符串；2）空串长度为零，空格串长度为所包括的空格字符的个数。

2、设s=‘I AM A STUDENT ’,t=‘GOOD’,q=‘WORKER’.求：1）StrLength（s）2）StrLength（t）3）SubString（s，8，7）4）SubSting（t，2，1）5）Index（s，’A’）6）index（s，t）7）Replace（s，’STUDENT’，q）8）Concat（SubString（s，6，2）,Concat（t，SubString（s，7，8）））答：1)StrLength（s）=142)StrLength（t）=43)SubString（s，8，7）= ‘STUDENT’4)SubSting（t，2，1）= ‘O’5)Index（s，’A’）= 36)index（s，t）= 07)Replace（s，’STUDENT’，q）= ‘I AM A WORKER ’8)Concat（SubString（s，6，2）,Concat（t，SubString（s，7，8）））= ‘A GOOD STUDENT’3、若串S1=‘ABCDEFG’, S2=‘9898’,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2 ,‘8’),length(S2)))其结果是多少答：ABC###G12344、下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。

请将空格处填上正确的语句。

void maxcomstr(orderstring *s,*t; int index, length){int i,j,k,length1,con;index=0;length=0;i=1;while (i<={j=1;while(j<={if (s[i]= =t[j]){k=1; length1=1; con=1;while(con)if (1) _ { length1=length1+1;k=k+1; }else (2) __;if (length1>length) { index=i; length=length1; }(3)____;}else (4) ___;}(5) __}}提示：算法采用顺序存储结构求串s和串t的最大公共子串。

1. 请简要描述一下Hadoop, Spark, MPI三种计算框架的特点以及分别适用于什么样的场景2. 请解释tcp连接建立过程，如果可能，请结合相应系统调用函数解释交互过程。

3. 给定一个整数的数组，相邻的数不能同时选，求从该数组选取若干整数，使得他们的和最大，要求只能使用o(1)的空间复杂度。

要求给出伪码。

4. 二分查找是常用的编程方法，请用完整代码实现该函数（不许调用库函数）void*bsearch(const void *key, const void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));5. 有编号1~100个灯泡，起初所有的灯都是灭的。

有100个同学来按灯泡开关，如果灯是亮的，那么按过开关之后，灯会灭掉。

如果灯是灭的，按过开关之后灯会亮。

现在开始按开关。

第1个同学，把所有的灯泡开关都按一次(按开关灯的编号：1,2,3,......100)。

第2个同学，隔一个灯按一次(按开关灯的编号：2,4,6,......,100)。

第3个同学，隔两个灯按一次(按开关灯的编号：3,6,9,......,99)。

...... 问题是，在第100个同学按过之后，有多少盏灯是亮着的？这些灯的编号是多少？要求给出解题思路或给出伪码。

6. 打长沙麻将在一开始，只有庄家可得到十四张牌，其余的人十三张。

现在庄家手里拿到十四张牌，他想请你写个程序帮忙判断一下，庄家是否已经胡牌。

如果你会打麻将，请忽略以下背景，如果不会，简单了解一下背景有助于理解本题：长沙麻将打法简单、节奏快速，极易胡牌。

长沙麻将共一百零八张牌：包括筒、索、万；不带东、南、西、北风、中、发、白。

：1、万子牌：从一万至九万，各4张，共36张。

2、筒子牌：从一筒至九筒，各4张，共36张。

也有的地方称为饼，从一饼到九饼。

3、束子牌：从一束至九束，各4张，共36张。

ACM 题型算法分类题目均来自：/JudgeOnline/主流算法：1.搜索//回溯2.DP（动态规划）3.贪心4.图论//Dijkstra、最小生成树、网络流5.数论//解模线性方程6.计算几何//凸壳、同等安置矩形的并的面积与周长7.组合数学//Polya定理8.模拟9.数据结构//并查集、堆10.博弈论1、排序1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380,1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379,1002（需要字符处理，排序用快排即可） 1007（稳定的排序） 2159（题意较难懂） 2231 2371（简单排序） 2388（顺序统计算法） 2418（二叉排序树）2、搜索、回溯、遍历1022 1111d 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 2386 1010,1011,1018,1020,1054,1062,1256,1321,1363,1501，1650,1659,1664,1753,2078,2083,2303,2310,2329简单：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742,1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426,不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197,2349,推荐：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709,1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170,2288, 2331, 2339, 2340,1979（和迷宫类似） 1980（对剪枝要求较高）3、历法1008 2080 （这种题要小心）4、枚举1012，1046， 1387， 1411， 2245， 2326， 2363， 2381，1054（剪枝要求较高），1650 （小数的精度问题）5、数据结构的典型算法容易：1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395, 不易：1145, 1177, 1195, 1227, 1661, 1834,推荐：1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010,2119, 2274, 1125(弗洛伊德算法) ，2421（图的最小生成树）6、动态规划1037 A decorative fence、1050 To the Max、1088 滑雪、1125 Stockbroker Grapevine、1141 Brackets Sequence、1159 Palindrome、1160 Post Office、1163 The Triangle、1458 Common Subsequence、1579 Function Run Fun、1887 Testing the CATCHER、1953 World Cup Noise、2386 Lake Counting7、贪心1042, 1065, 1230, 1323, 1477, 1716, 1784,1328 1755（或用单纯形方法），2054，1017， 1328，1862， 1922 ，2054， 2209， 2313， 2325， 2370。

动态规划公式-----机器分配问题F[I,j]:=max(f[i-1,k]+w[i,j-k])2. 资源问题2------01背包问题F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);3. 线性动态规划1-----朴素最长非降子序列F[i]:=max{f[j]+1}4. 剖分问题1-----石子合并F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);5. 剖分问题2-----多边形剖分F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]);6. 剖分问题3------乘积最大f[i,j]:=max(f[k,j-1]*mult[k,i]);7. 树型动态规划1-----加分二叉树 (从两侧到根结点模型) F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]}8. 递推天地2------数的划分f[i,j]:=f[i-j,j]+f[i-1,j-1];9. 线型动态规划3-----最长公共子串，LCS问题f[i,j]={0 (i=0)&(j=0);f[i-1,j-1]+1 (i>0,j>0,x[i]=y[j]);max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x[i]<>y[j]);10. 资源问题4-----装箱问题(判定性01背包)f[j]:=(f[j] or f[j-v[i]]);11. 数字三角形1-----朴素の数字三角形f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);12. 双向动态规划1数字三角形3-----小胖办证f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])13. 数字三角形4-----过河卒//边界初始化f[i,j]:=f[i-1,j]+f[i,j-1];14. 递推天地3-----情书抄写员f[i]:=f[i-1]+k*f[i-2]15 线性动态规划5-----隐形的翅膀min:=min{abs(w[i]/w[j]-gold)};if w[i]/w[j]16 最短路1-----Floydf[i,j]:=max(f[i,j],f[i,k]+f[k,j]);ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];17 线性动态规划------合唱队形两次F[i]:=max{f[j]+1}＋枚举中央结点1. 资源问题1-----机器分配问题F[I,j]:=max(f[i-1,k]+w[i,j-k])2. 资源问题2------01背包问题F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]);3. 线性动态规划1-----朴素最长非降子序列F[i]:=max{f[j]+1}4. 剖分问题1-----石子合并F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]);5. 剖分问题2-----多边形剖分F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]);6. 剖分问题3------乘积最大f[i,j]:=max(f[k,j-1]*mult[k,i]);7. 树型动态规划1-----加分二叉树 (从两侧到根结点模型)F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]}8. 递推天地2------数的划分f[i,j]:=f[i-j,j]+f[i-1,j-1];9. 线型动态规划3-----最长公共子串，LCS问题f[i,j]={0 (i=0)&(j=0);f[i-1,j-1]+1 (i>0,j>0,x[i]=y[j]);max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x[i]<>y[j]);10. 资源问题4-----装箱问题(判定性01背包)f[j]:=(f[j] or f[j-v[i]]);11. 数字三角形1-----朴素の数字三角形f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]);12. 双向动态规划1数字三角形3-----小胖办证f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j])13. 数字三角形4-----过河卒//边界初始化f[i,j]:=f[i-1,j]+f[i,j-1];14. 递推天地3-----情书抄写员f[i]:=f[i-1]+k*f[i-2]15 线性动态规划5-----隐形的翅膀min:=min{abs(w[i]/w[j]-gold)};if w[i]/w[j]16 最短路1-----Floydf[i,j]:=max(f[i,j],f[i,k]+f[k,j]);ans[q[i,j,k]]:=ans[q[i,j,k]]+s[i,q[i,j,k]]*s[q[i,j,k],j]/s[i,j];17 线性动态规划------合唱队形两次F[i]:=max{f[j]+1}＋枚举中央结点。

z函数和前缀函数全文共四篇示例，供读者参考第一篇示例：z函数和前缀函数是算法领域中常用的两种字符串匹配技术，它们在处理字符串匹配和模式匹配问题时具有重要作用。

本文将介绍z函数和前缀函数的概念、原理和应用，希望读者能够对这两种技术有一个全面的了解。

一、z函数的概念及原理1.1 z函数的定义：z函数是一种用于求解字符串匹配中最长公共前缀的函数。

给定一个字符串s，z函数值z[i]表示以s[i]为起始的子串与原字符串s的最长公共前缀长度。

具体来说，z函数的值z[i]满足以下条件：z[i] = max{k | s[0,k-1] = s[i,i+k-1]}要计算z函数值，可以采用以下算法：首先设置两个指针l和r，分别指向当前匹配的子串的最左端和最右端，然后逐个比较s[l]与s[r]，若s[l]等于s[r]，则继续向右移动r和左移动l，直到不满足条件为止。

z[i]的值就是r-l的长度。

z函数在字符串匹配和模式匹配中有着广泛的应用。

通过求解z函数值，我们可以实现高效的字符串匹配算法，例如KMP算法和Rabin-Karp算法，这些算法可以在O(m+n)的时间复杂度内完成字符串匹配操作，提高了匹配效率。

2.2 前缀函数的计算：前缀函数在字符串匹配和模式匹配问题中也有着重要的应用。

它可以帮助我们有效地求解串匹配时的重复子串，从而提高匹配的效率。

前缀函数也可以用于求解最长回文子串和最长回文子序列等问题。

三、z函数与前缀函数的比较3.1 相似点：z函数与前缀函数都是用于求解字符串匹配中的最长公共前缀或最长相同前缀后缀的技术，它们在实际应用中具有一定的相似性。

尽管z函数和前缀函数都是求解字符串匹配问题的技术，但它们的计算方法和具体应用略有不同。

z函数是从左往右计算的，而前缀函数是从右往左计算的，因此在实际应用中可能会有不同的适用场景。

四、z函数和前缀函数在实际应用中的示例4.1 KMP算法：KMP算法是一种基于z函数或前缀函数的高效字符串匹配算法。

2020年浙江省新高考选考科目名师重组卷2信息技术试题一、选择题（本大题共12小题，每小题2分，共24分每小题列出的四个备选项中只有一个是符合题目要求的，不选、多选、错选均不得分）1.下列关于信息的说法，不正确的是（）A.手机扫描二维码过程属于信息的获取B.“盲人摸象”的事例说明信息具有真伪性C.点赞“浙江教育”公众号中的文章属于核心刊物评价D.游戏中体验到的“身临其境”感觉采用的是虚拟现实技术2.下列有关网络协议的描述，正确的是（）A.FTP是超文本传输协议的简称B.FTP用于浏览器与WEB服务器之间的信息传输C.SMTP用于实现将电子邮件发送到收件人的计算机中D.SMTP是简单邮件传输协议的简称3.下列应用中，体现人工智能技术的是（）①饮水机自动保温、加热功能②在手机上利用触摸屏手写输入文字③用微信进行语音聊天④用智能手机将视频分享到朋友圈⑤利用在线翻译将一段中文翻译成法语A.②③B.①④⑤C.②⑤D.①③⑤4.在Ultraedit软件中观察字符内码，部分界面如图所示下列说法中，不正确的是（）A.大写英文字符“J”的十六进制码为50HB.全部字符中有3个字符采用GB2312编码C.全部字符一共占用11个字节的存储空间D小写英文字母“o”的十进制编码为1115.使用Gold Wave软件打开某音频文件，其部分编辑界面如图所示：下列说法正确的是（）A.该音频的采样频率为1411kHz，量化位数为16位B.“全选”左声道，单击“删除”后文件存储容量变为原来的l/2C插入5秒“静音”，以当前参数保存，音频文件容量将保持不变D.当前状态下执行“删除”操作，以当前参数保存，文件存储容量不变6有一段时长30秒、采样频率为44.1kHz、量化位数为8位、未经压缩的双声道Wave音频文件，该音频文件的存储容量约为（）A.2.5MB B 861KB C.240KB D.32KB7.某算法的部分流程图如图。

执行这部分流程，分别输入45，50，55，则输出值依次为（）A.6，5B.5，7，7C.6，7D.6，7，78有如下ⅤB程序段：Dim i As Integer, j As Integer, a(1 To 5) As IntegerFor i = 1 To 5a(i) = Int(Rnd*5+1)For j =1 To i – lIf a(i) = a(j) Theni = i-1: Exit ForEnd ifNext jNext i执行程序后，数组中的数据可能是（）A.1 4 3 2 5B.1 1 3 5 4C.1 4 5 6 3D.2 3 4 5 5 9有如下VB程序段：s = “1234567899”g = “”For i = 1 To 3n = Len(s)x = Int (Rnd * n) + 1g = g + Mid (s, x, 1)s = Mid (s , 1, x-1) + Mid (s, x+1, n - x)Next i在程序执行时，若变量x的值依次为3,3,6，则最终变量g的值为（）A. “336”B. “346”C. “338”D.1510.有如下VB程序段：For i = 1 To 3For j = 1 To 5-iIf a(j) > a(j+1) Thent = a(j):a(j) = a(j+1):a(j+1) = tEnd IfText1. Text = Text1. Text + Str(a(i))Next i数组元素a(1)到a(5)的值依次为“3,9,6,8,4”。