ACM/ICPC算法训练：后缀数组与最长公共前缀

"这篇文档是南京理工大学ACM/ICPC集训队整理的《ACM/ICPC算法训练教程》，涵盖了算法基础、数据结构、数论、计算几何和图算法等多个方面，旨在帮助ACM/ICPC初学者和编程爱好者提升算法与数据结构能力。" 在ACM/ICPC竞赛中，解决程序设计问题的关键在于理解和应用各种算法。以下是教程中提到的一些重要知识点： **算法基础** 1. **穷举（枚举）法**：在问题的解空间内遍历所有可能的解，适用于解空间小的问题。 2. **递归法**：通过函数自身调用解决问题，通常与分治法结合，如斐波那契数列。 3. **分治法**：将大问题分解为小问题分别解决，然后合并结果，如快速排序、归并排序。 4. **贪心法**：每一步选择局部最优解，期望全局最优，如霍夫曼编码。 5. **模拟法**：按照问题的规则直接实现过程，适用于复杂规则或动态过程。 **数据结构** 1. **基本数据结构**：包括数组、链表、栈、队列等。 2. **查找与排序**：二分查找、哈希查找、冒泡排序、快速排序等。 3. **并查集**：用于处理集合合并与查询，常用于解决连通性问题。 4. **堆（优先队列）**：支持快速插入、删除最大（或最小）元素，如堆排序。 5. **Hash表**：快速查找、插入和删除操作，实现O(1)的平均时间复杂度。 6. **线段树**：用于区间查询和修改，如区间最值、区间加减操作。 **数论** 1. **素数问题**：欧几里得算法用于计算最大公约数，扩展欧几里得算法求模逆和线性同余方程解。 2. **整数因子分解**：找到一个数的质因数分解，对密码学等领域至关重要。 **计算几何** 1. **矢量基础**：向量的加减乘运算，用于表示位置、速度等。 2. **线段相交检测**：判断两条线段是否交叉，基础的几何问题。 3. **寻找凸包**：找到包含所有点的最小凸多边形，如 Gift Wrapping 算法或 Graham's Scan。 4. **最近点对**：在一组点集中找到距离最近的两点对，可应用于碰撞检测等。 **图算法** 1. **最小生成树**：Prim算法和Kruskal算法用于找到无权或有权图的最小生成树。 2. **其他图算法**：如Dijkstra算法（单源最短路径）、Floyd-Warshall算法（所有对最短路径）等。 这些知识点是ACM/ICPC竞赛中常见的问题解决工具，掌握它们对于参赛者来说至关重要。通过学习和实践，参赛者能提高解决问题的能力，并在竞赛中取得好成绩。