本文介绍了KMP算法及其扩展应用。主要内容包括： KMP算法通过预处理模式串生成next数组，利用已匹配信息避免回溯，将字符串匹配优化至线性时间复杂度O(n+m)。文章提供了KMP模板代码实现。 扩展KMP（Z函数）用于求解模式串与文本串每个后缀的最长公共前缀，给出了算法定义和实现模板。 简要提及马拉车(Manacher)算法（未详细展开）并附模板代码。 通过经典例题展示KMP应用，如利用lps数

下面是一些典型的例题，涵盖了动态规划、贪心算法和回溯算法等常见算法问题。问题描述：给定一个区间列表，找到可以安排的最大活动数量，使得它们不会相互冲突。问题描述：给定一个整数数组，找到一个连续子数组，使得子数组的和最大。问题描述：给定一个集合，找到所有可能的子集。