KMP和Manacher算法
Manacher算法
- 预处理：统一奇偶长度
- 回文串有奇数长度（如”aba”）和偶数长度（如”abba”）之分，这会给统一处理带来麻烦。
- Manacher算法通过在原始字符串的每个字符之间以及首尾插入一个原字符串中不存在的特殊字符（通常用
#）来进行预处理。例如，"abba"会被处理成"#a#b#b#a#"。 - 这样做的好处是：无论原字符串如何，新字符串的长度总是奇数，所有回文子串都变成了奇数长度，从而可以统一以每个字符为中心进行扩展检查。
- 利用回文对称性
- 算法维护一个回文半径数组
P（也称为辅助数组），P[i]表示以新字符串中第i个字符为中心的最长回文子串的半径（包含中心字符本身）。例如，对于字符串"#a#b#a#"，以中间的b（位于索引4）为中心，其回文半径是4。 - 关键在于，算法在从左至右遍历字符串时，会动态维护一个当前已知的最右回文边界
R以及达到该边界的中心位置C。 - 当遍历到位置
i时，如果i在当前最右边界R之内，则可以找到i关于中心C的对称点j。根据回文的对称性，可以利用P[j]的值来快速确定P[i]的一个初始最小值，从而避免从1开始逐个字符扩展，大大减少了比较次数。这通常归纳为几种情况：- 如果
j的回文区域完全包含在C的大回文区域内，那么P[i]直接等于P[j]。 - 如果
j的回文区域超出了C的大回文区域，那么P[i]至少为R - i。 - 如果
j的回文区域恰好到达C的大回文区域边界，则P[i]的初始值设为R - i，并需要继续向两侧扩展检查。
- 如果
- 如果
i超出了R，则无法利用对称性，只能进行朴素的中心扩展。 - 无论哪种情况，在获得初始值后，算法都会尝试继续向两侧扩展，以检查是否能得到更长的回文串，并相应地更新
R和C。
- 算法维护一个回文半径数组
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 岁迹！
相关推荐
2026-06-27
一些基础的数据结构
动态数组 装箱：装箱是指将值类型转换为引用类型的过程。值类型（如 int、char、struct 等）通常存储在栈上，而引用类型存储在堆上。当进行装箱操作时，会在堆上为值类型创建一个对象实例，并将值类型的值复制到该对象中，最后返回这个对象的引用。 拆箱：拆箱则是将引用类型转换为值类型的过程。它需要先检查引用类型是否为某个特定值类型的装箱实例，然后将堆上对象中存储的值复制到栈上的新值类型变量中。 装箱开销：装箱操作会在堆上分配内存，并且需要复制值类型的值，这会带来一定的性能开销，尤其是在频繁进行装箱操作时，会导致内存分配和垃圾回收的压力增加。 拆箱开销：拆箱操作需要进行类型检查，确保引用类型确实是某个值类型的装箱实例，这也会带来一定的性能开销。 动态数组指的是是大小能在程序运行期间动态调整的数组，可根据实际需求增添或删减元素。与固定大小的数组不同，动态数组能够灵活应对元素数量的变化，从而更高效地管理内存。以下通过自定义的类实现动态数组，使用泛型类，来进行动态数组的实现，这样可以根据数组的类型，实现相应的功能，同时实现IEnumerable接口，可以被foreach循环遍历...
2026-06-27
图
图结构图 = 点 + 边 点结构1234567891011121314public class Node{ public int value; //点值 public int in; //入度 public int out; //出度 public List<Node> nexts; //从该点能找到邻居 public List<Edge> edges; //能找到邻居的边集 public Node(int v){ value = v; in = 0; out = 0; nexts = new List<Node>(); edges = new List<Edge>(); }} 边结构12345678910public class Edge{ public int weight;//权重 public Node from; //那个点出发 public Nod...
2026-06-27
前缀树
前缀树前缀树（Trie，发音类似 “try”）是一种树形数据结构，用于高效存储和检索字符串集合。它的核心特点是共享公共前缀，适用于自动补全、拼写检查、IP路由等场景。 1. 前缀树的特点 节点结构：每个节点存储一个字符，从根节点到某个节点的路径构成一个字符串。 共享前缀：不同单词的相同前缀会共享同一条路径，节省空间。 快速查找：查找时间复杂度为 O(L)（L 是单词长度），比哈希表更适合前缀匹配。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104public class Node1{ public int pass; public int end; public Node1[] Next;//存...
2026-06-27
归并排序
迭代归并排序123456789101112131415161718192021222324252627282930313233343536public void Sort(int[] arrs, int L, int R) { int step = 1; int N = arrs.length; while (step < N) { int left = 0; while (left < N) { int mid = left + step - 1; if (mid >= N) break; int right = Math.min(left + 2 * step - 1, N - 1); // 修正右边界计算 Merge(arrs, left, mid, right); // 修正方法调用参数 left = right + 1; &#...
2026-06-27
2叉树
12345678910* public class Node {* public int val;* public Node left;* public Node right;* public Node(int val=0, Node left=null, Node right=null) {* this.val = val;* this.left = left;* this.right = right;* }* } 非递归实现遍历使用栈进行先序遍历 头 - 左 - 右1234567891011121314151617181920public List<int> presort(Node head){ List<int> result = new List<int>(); Stack<Node> nodes = new Stack<Node>(); if (...
2026-06-27
异或相关面试题
异或：2进制相同为0，不同为1。同时满足交换律和结合律 0 ^ N = N N ^ N = 0 同或：2进制相同为1，不同为0 题一：如何不用额外遍历交换两个数默认情况是使用临时变量来存储一个数，最后交换。在此处我们使用异或运算，依靠异或的下列特点来进行交换。 123456789//默认情况int tmp = a;a = b;b = tmp;//依靠异或,但是条件是，A，B指向的是不同的内存区域a = a ^ b;b = a ^ b;a = a ^ b; 0 ^ N = N N ^ N = 0 题二：一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并且打印这种数（LeetCode136）默认情况是使用字典进行存储，将每种数作为键进行存储，值则为出现的次数，最后循环找到奇数次的那种数. 创建一个变量赋值为 0，使用该变量异或遍历每一个数组的值，即可。 1234567891011static void Main(string[] args){ int[] arrs = { 1, 1,2, 2, ...