前言：
本系列是学习了董晓老师所讲的知识点做的笔记
董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)
动态规划系列（还没学完）
【算法】动态规划之线性DP问题-CSDN博客
【算法】动态规划之背包DP问题（2024.5.11）-CSDN博客
【算法】动态规划之背包DP与树形DP-CSDN博客
最小表示法
P1368 【模板】最小表示法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
找出字符串S的循环同构串中字典序最小的那一个
循环同构串含义：字符串S中选定一个位置i满足 S[i-n]+S[1-i-1]=T，则T是S的循环同构串。S=“bcad"，其循环同构串有“bcad"、“cadb"、“adbc”、“dbca”当 i=3 时，得到字典序最小的循环同构串是“adbc”。
解题技巧：复制加倍，破环成链；使用三指针控制，分类跳转，及时淘汰劣质选项
int n;
char s[N];
int get_min(){
for(int i=1;i<=n;i++) s[n+i]=s[i];
int i = 1, j = 2, k = 0;
while(i<=n && j<=n){
for(k=0; k<n&&s[i+k]==s[j+k]; k++);
s[i+k]>s[j+k] ? i=i+k+1 : j=j+k+1;
if(i==j) j++;
}
return min(i, j);
}字符串哈希
核心：
把字符串映射成一个p进制数字
哈希碰撞:
两字符串不一样，Hash 函数值却一样
解决哈希碰撞的方法:
巧妙设置 p和 M 的值，保证p与M互质。p 通常取质数 131 或 13331.M 通常取大整数 2的64次方，把哈希函数值h定义为ULL，超过则自动溢出等价于取模。
知识点
求一个字符串的哈希值相当于求前缀和.
求一个字符串的子串的哈希值相当于求区间和.
核心代码
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int P = 131;
// p[i]=P^i, h[i]=s[1~i]的hash值
ULL p[N], h[N];
// 预处理 hash函数的前缀和
void init() {
p[0] = 1, h[0] = 0;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + s[i];
}
}
// 计算s[l~r]的 hash值
ULL get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
// 判断两子串是否相同
bool substr(int l1, int r1, int l2, int r2) {
return get(l1, r1) == get(l2, r2);
}
KMP算法
//求取next函数
ne[1] = 0;
for(int i = 2, j = 0; i <= n; i ++){
while(j && P[i] != P[j+1]) j = ne[j];
if(P[i] == P[j+1]) j ++;
ne[i] = j;
}
// KMP匹配
for(int i = 1, j = 0; i <= m; i ++){
while(j && S[i] != P[j+1]) j = ne[j];
if(S[i] == P[j+1]) j ++;
if(j == n) printf("%d\n", i-n+1);
}扩展KMP（Z函数）（重新敲一次还是不太懂）
P5410 【模板】扩展 KMP/exKMP（Z 函数） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
算法流程
计算完前i-1个z函数，维护盒子[l,r]，则s[l,r]=s[1,r-1+1]
1. 如果i≤r(在盒内)，则有 s[i,r]= s[i-l+1],r[i-l+1]。
(1)若z[i-l+ 1|<r-i+1，则z[i]=z[i-l+ 1|。
(2)若z[i-l+ 1|≥r-i+1，则令z[i]=r-i+1，从r+1往后暴力枚举
2.如果i>r(在盒外)，则从i开始暴力枚举。
3.求出z[i]后，如果i+z[i]-1>r，则更新盒子l=i,r=i+ z[i]-1
核心代码
void get_z(char*s,int n){
z[1]=n;
for(int i=2,l,r=0;i<=n;i++){
if(i<=r)z[i]=min(z[i-l+1],r-i+1);
while(s[1+z[i]]==s[i+z[i]])z[i]++;
if(i+z[i]-1>r)l=i,r=i+z[i]-1;
}
}
void get_p(char*s,int n,char*t,int m){
for(int i=1,l,r=0;i<=m;i++){
if(i<=r)p[i]=min(z[i-l+1],r-i+1);
while(1+p[i]<=n&&i+p[i]<=m
&&s[1+p[i]]==t[i+p[i]])p[i]++;
if(i+p[i]-1>r)l=i,r=i+p[i]-1;
}
}Manacher算法
P3805 【模板】manacher - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
知识点
1.作用：在 O(n) 的时间内求出一个字符串中的最长回文串
2.在字符之间和串两端插入#，改造后都变成奇回文串，方便统一处理。
3.回文半径：以i为中心的最长回文串的长度的一半叫回文半径
4.加速盒子：维护右端点最靠右的盒子，盒内加速，盒外暴力。
5.原串的最长回文串=新串的最大半径-1。
核心代码
scanf("%s", a + 1);
int n = strlen(a + 1), k = 0;
s[0] = '$', s[++k] = '#';
for (int i = 1; i <= n; i++)
s[++k] = a[i], s[++k] = '#';
n = k;
void get_d(char* s, int n) {
d[1] = 1;
for (int i = 2, l, r = 1; i <= n; i++) {
if (i <= r) d[i] = min(d[r - i +l], r - i + 1);
while (s[i - d[i]] == s[i + d[i]])d[i]++;
if (i + d[i] - 1 > r) l = i - d[i] + 1, r = i + d[i] + 1;
}
}三者对比
