/AlgorithmTemplate

The algorithim template for the competation ACM/ICPC.

Primary LanguageC++

AlgorithimTemplate

1. 简介

收录ACM常用算法的模板，以及应用算法的练习题。

2. 分类

2.1 字符串

2.1.1 manacher算法

  • 简介：求一个字符串的最长回文子串
  • 时间复杂度：O(n)
  • 原理
1. 在每个字符之间插入一个不会出现的字符（例如#）
2. 记录当前求得的所有回文子串中，所能触及的最右的位置max_right，以及这个回文子串的中心位置max_right_pos
3. 遍历求解RL[i], 为以i为中心点，最长回文子串的左半部分长度（包括自己）
4. 求解RL[i]的时候，可以利用max_right_pos以及i相对于max_right_pos的对称点j（因为RL[j]以及求出）
  • 习题

2.1.2 trie树

  • 简介：字符串哈希的变种，用树记录出现过的字符串，每个节点为一个字母。

2.1.3 KMP算法

  • 简介：有字符串str，str2，求str2是否在str中出现过
  • 核心：求next数组，next[i] = j, 从位置0-i的字符串str，str的前缀和str的后缀相同的最长长度的时候，j为str前缀的最后一个位置。