Ciallo～(∠・ω< )⌒☆

这里是我整理出来的、用C艹描述的过去我学到过的一些在算法竞赛中常用的数据结构和算法的通用模板。

内容较多，既有基础数据结构如哈希表，基础算法如DP,贪心，BFS、DFS、各种背包问题；也有进阶数据结构如线段树、并查集等。希望能给大家刷题时带来些许帮助。

(❁´◡`❁)碎碎念就到这里，以下是正文：

常见算法数据结构模板（C++描述）

1. 常用头文件和基础定义

#include <bits/stdc++.h>
using namespace std;

#define int long long           // 统一将 int 视为 long long（64位）
#define ll long long            // 64 位整数
#define i64 long long           // 别名，便于快速切换
#define i128 __int128_t         // 128 位有符号整数
#define u128 __uint128_t        // 128 位无符号整数

#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()

const int INF = 0x3f3f3f3f;                   // int 最大常量
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;        // long long 最大常量
const i128 INFI128 = ((i128)1 << 126);        // 128位极大值示例

//128位整数，__int128_t 是 GCC/Clang 扩展，不能直接用 cin/cout，需要自己写输入输出函数，例如：
void read_i128(i128 &x) {
    string s; cin >> s;
    bool neg = false; int i = 0;
    if (s[0] == '-') neg = true, i = 1;
    x = 0;
    for (; i < (int)s.size(); i++) x = x * 10 + (s[i] - '0');
    if (neg) x = -x;
}

void print_i128(i128 x) {
    if (x < 0) { cout << '-'; x = -x; }
    if (x > 9) print_i128(x / 10);
    cout << (int)(x % 10);
}

2. 快速读写模板

// C++14及以后版本，使用ios优化
ios::sync_with_stdio(false);
cin.tie(nullptr);

3. 并查集（Union Find）

struct UnionFind {
    vector<int> fa;
    UnionFind(int n) : fa(n+1) {
        iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    void unite(int x, int y) {
        int fx = find(x), fy = find(y);
        if(fx != fy) fa[fx] = fy;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

4. 树的DFS遍历模板

const int N = 1e5 + 10;
vector<int> G[N];
bool visited[N];

void dfs(int u) {
    visited[u] = true;
    // 处理节点u
    for(int v : G[u]) {
        if(!visited[v]) dfs(v);
    }
}

5. BFS遍历模板（最短路等）

queue<int> q;
bool visited[N];

void bfs(int start) {
    memset(visited, 0, sizeof(visited));
    visited[start] = true;
    q.push(start);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        // 处理节点u
        for(int v : G[u]) {
            if(!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

6. 快速幂（mod）

ll qpow(ll base, ll exp, ll mod) {
    ll res = 1 % mod;
    while(exp > 0) {
        if(exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

7. 素数筛（埃拉托斯特尼筛法）

const int MAXN = 1e7+10;
bool is_prime[MAXN];
void sieve(int n) {
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    for(int i=2; i<=n; i++) {
        if(is_prime[i]) {
            for(int j=i*2; j<=n; j+=i) {
                is_prime[j] = false;
            }
        }
    }
}

8. 前缀和

const int N = 1e6+10;
int a[N], prefix[N];
int n;

void build_prefix() {
    prefix[0] = 0;
    for(int i=1; i<=n; i++) {
        prefix[i] = prefix[i-1] + a[i];
    }
}
// 区间和：[l, r]
int range_sum(int l, int r) {
    return prefix[r] - prefix[l-1];
}

9. 单调栈（求单调区间、直方图最大矩形等）

stack<int> st;
vector<int> a; // 输入序列
int n;

void mono_stack() {
    // 示例：求每个元素左边第一个比它小的元素位置
    vector<int> left_smaller(n, -1);
    for(int i=0; i<n; i++) {
        while(!st.empty() && a[st.top()] >= a[i]) st.pop();
        left_smaller[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
}

10. 二分查找模板

int binary_search(int target) {
    int l = 0, r = n - 1;
    while(l <= r) {
        int mid = l + (r-l)/2;
        if(a[mid] == target) return mid;
        else if(a[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1; // 未找到
}

11. LIS（最长递增子序列） — O(n log n)

vector<int> a; // 输入序列
vector<int> dp; // 维护LIS序列

int LIS() {
    for(auto x : a) {
        auto it = lower_bound(dp.begin(), dp.end(), x);
        if(it == dp.end()) dp.push_back(x);
        else *it = x;
    }
    return (int)dp.size();
}

12. 堆优先队列（优先队列）

priority_queue<int> pq; // 大顶堆
priority_queue<int, vector<int>, greater<int>> min_pq; // 小顶堆

13. Dijkstra 最短路

struct Edge { int to, w; };
const int N = 1e5+10;
vector<Edge> G[N];
ll dist[N];
bool vis[N];
const ll INF = 1e15;

void dijkstra(int s, int n) {
    for(int i=1; i<=n; i++) dist[i] = INF, vis[i] = false;
    dist[s] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0, s});

    while(!pq.empty()) {
        auto [d,u] = pq.top(); pq.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(auto &e : G[u]) {
            int v = e.to; ll w = e.w;
            if(dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

14. 拓扑排序

const int N = 1e5+10;
vector<int> G[N];
int indeg[N];
queue<int> q;
int n;

void topo_sort() {
    for(int i=1; i<=n; i++)
        if(indeg[i] == 0) q.push(i);

    while(!q.empty()) {
        int u = q.front(); q.pop();
        // 处理节点u
        for(int v : G[u]) {
            indeg[v]--;
            if(indeg[v] == 0) q.push(v);
        }
    }
}

15. 树的重心求法

int n;
vector<int> G[N];
int size[N], maxSubtree[N], centroid;

void get_centroid(int u, int fa) {
    size[u] = 1;
    maxSubtree[u] = 0;
    for(int v : G[u]) {
        if(v == fa) continue;
        get_centroid(v, u);
        size[u] += size[v];
        maxSubtree[u] = max(maxSubtree[u], size[v]);
    }
    maxSubtree[u] = max(maxSubtree[u], n - size[u]);
    if(centroid == 0 || maxSubtree[u] < maxSubtree[centroid])
        centroid = u;
}

16. 字符串KMP算法

vector<int> getNext(const string &s) {
    int n = (int)s.size();
    vector<int> nxt(n);
    nxt[0] = 0;
    int j = 0;
    for(int i=1; i<n; i++) {
        while(j > 0 && s[i] != s[j]) j = nxt[j-1];
        if(s[i] == s[j]) j++;
        nxt[i] = j;
    }
    return nxt;
}

17. 堆优化的Prim算法

struct Edge { int to, w; };
vector<Edge> G[N];
bool vis[N];
int dist[N];

int prim(int n) {
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<=n; i++) dist[i] = INF;
    dist[1] = 0;
    int res = 0;
    for(int i=1; i<=n; i++) {
        int u = -1, minDist = INF;
        for(int j=1; j<=n; j++) {
            if(!vis[j] && dist[j] < minDist) {
                u = j;
                minDist = dist[j];
            }
        }
        if(u == -1) return -1;
        vis[u] = true;
        res += dist[u];
        for(auto &e : G[u]) {
            if(!vis[e.to] && e.w < dist[e.to])
                dist[e.to] = e.w;
        }
    }
    return res;
}

算法常见题型通用模板合集（C++）

1. 递归与回溯模板

void backtrack(/* 参数 */) {
    // 终止条件
    if (/* 目标条件 */) {
        // 处理结果
        return;
    }

    for (/* 选择范围 */) {
        // 做选择
        // 标记状态
        backtrack(/* 新状态 */);
        // 撤销选择（回溯）
    }
}

2. 双指针模板

int left = 0, right = 0;
// 示例：在有序数组中找满足条件的区间
while (right < n) {
    // 移动右指针，扩展区间
    while (/* 区间不满足条件 */ && left <= right) {
        // 收缩左指针
        left++;
    }
    // 处理当前区间[left, right]
    right++;
}

3. 滑动窗口模板

int left = 0, right = 0;
while (right < n) {
    // 处理加入元素 a[right]
    right++;
    while (/* 窗口不满足条件 */) {
        // 移除元素 a[left]
        left++;
    }
    // 处理符合条件的窗口 [left, right-1]
}

4. 分治法模板

// 经典分治例：归并排序
void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    // 合并两个有序区间
    merge(l, mid, r);
}

5. 二分搜索模板

int l = 0, r = n - 1;
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) // check是某个条件函数
        r = mid - 1;
    else
        l = mid + 1;
}
// 返回最小满足条件的位置 l 或最大不满足条件的位置 r

6. 状压DP模板

int n; // 状态中元素个数
int dp[1 << n];

// 初始化
dp[0] = 0;
for (int s = 0; s < (1 << n); s++) {
    for (int i = 0; i < n; i++) {
        if (!(s & (1 << i))) {
            int ns = s | (1 << i);
            dp[ns] = min(dp[ns], dp[s] + cost(i, s)); // cost函数根据题意
        }
    }
}

7. 树形DP模板（以树上求最大距离为例）

vector<int> G[N];
int dp[N];

void dfs(int u, int fa) {
    dp[u] = 0;
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs(v, u);
        dp[u] = max(dp[u], dp[v] + 1);
    }
}

8. 单调栈处理下一个更大/更小元素模板

stack<int> st; // 存索引
for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.top()] < a[i]) {
        // a[i]是st.top()的下一个更大元素
        st.pop();
    }
    st.push(i);
}

9. 贪心框架模板

sort(items.begin(), items.end(), [](auto &a, auto &b) {
    return /* 贪心优先级 */;
});
for (auto &item : items) {
    if (/* 满足条件 */) {
        // 选取item
    }
}

10. 线段树模板（区间加、区间求和）

struct SegTree {
    vector<int> tree, lazy;
    int n;
    SegTree(int _n) : n(_n) {
        tree.resize(4*n);
        lazy.resize(4*n);
    }
    void pushdown(int rt, int l, int r) {
        if (lazy[rt] != 0) {
            int mid = (l + r) / 2;
            tree[rt*2] += lazy[rt] * (mid - l + 1);
            tree[rt*2+1] += lazy[rt] * (r - mid);
            lazy[rt*2] += lazy[rt];
            lazy[rt*2+1] += lazy[rt];
            lazy[rt] = 0;
        }
    }
    void update(int rt, int l, int r, int L, int R, int val) {
        if (L <= l && r <= R) {
            tree[rt] += val * (r - l + 1);
            lazy[rt] += val;
            return;
        }
        pushdown(rt, l, r);
        int mid = (l + r) / 2;
        if (L <= mid) update(rt*2, l, mid, L, R, val);
        if (R > mid) update(rt*2+1, mid+1, r, L, R, val);
        tree[rt] = tree[rt*2] + tree[rt*2+1];
    }
    int query(int rt, int l, int r, int L, int R) {
        if (L <= l && r <= R) return tree[rt];
        pushdown(rt, l, r);
        int mid = (l + r) / 2, res = 0;
        if (L <= mid) res += query(rt*2, l, mid, L, R);
        if (R > mid) res += query(rt*2+1, mid+1, r, L, R);
        return res;
    }
};

背包、贪心、分治等算法模板（C++）

一、背包问题模板

1.01 01背包（经典）

const int N = 1e5+10;
int dp[N]; // dp[j]: 容量为j时的最大价值
int n, W; // 物品数，背包容量
int w[N], v[N]; // 重量、价值

void zero_one_knapsack() {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = W; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
}

1.02 完全背包

void complete_knapsack() {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = w[i]; j <= W; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
}

1.03 多重背包（折半拆分/二进制拆分）

void multiple_knapsack() {
    for (int i = 1; i <= n; i++) {
        int num = s[i]; // 数量
        for (int k = 1; num > 0; k <<= 1) {
            int use = min(k, num);
            num -= use;
            int ww = use * w[i], vv = use * v[i];
            for (int j = W; j >= ww; j--) {
                dp[j] = max(dp[j], dp[j - ww] + vv);
            }
        }
    }
}

1.04 01背包求方案数（计数）

int dp[N]; // dp[j]: 容量j的方案数
const int MOD = 1e9+7;

void zero_one_knapsack_count() {
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = W; j >= w[i]; j--) {
            dp[j] = (dp[j] + dp[j - w[i]]) % MOD;
        }
    }
}

二、贪心算法模板

2.01 贪心求区间覆盖/调度问题

struct Interval {
    int start, end;
};
bool cmp(const Interval &a, const Interval &b) {
    return a.end < b.end; // 按结束时间排序
}

void interval_scheduling(vector<Interval> &intervals) {
    sort(intervals.begin(), intervals.end(), cmp);
    int count = 0;
    int last_end = INT_MIN;
    for (auto &itv : intervals) {
        if (itv.start >= last_end) {
            count++;
            last_end = itv.end;
        }
    }
    cout << count << "\n";
}

2.02 贪心分配问题

// 示例：按贪心优先级排序，分配资源
struct Item {
    int cost, value;
};
bool cmp(const Item &a, const Item &b) {
    return a.value * b.cost > b.value * a.cost; // 比如按性价比排序
}

void greedy_assign(vector<Item> &items) {
    sort(items.begin(), items.end(), cmp);
    // 依次分配资源
    for (auto &item : items) {
        // 分配逻辑
    }
}

2.03 Huffman编码

struct Node {
    int weight;
    int left, right;
};
priority_queue<int, vector<int>, greater<int>> pq;

void huffman(vector<int> &weights) {
    for (int w : weights) pq.push(w);
    int ans = 0;
    while (pq.size() > 1) {
        int x = pq.top(); pq.pop();
        int y = pq.top(); pq.pop();
        ans += x + y;
        pq.push(x + y);
    }
    cout << ans << "\n";
}

三、分治算法模板

3.01 归并排序模板（分治思想）

void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    // 合并[l, mid]和[mid+1, r]两个有序区间
    vector<int> temp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) temp.push_back(a[i++]);
        else temp.push_back(a[j++]);
    }
    while (i <= mid) temp.push_back(a[i++]);
    while (j <= r) temp.push_back(a[j++]);
    for (int k = l; k <= r; k++) a[k] = temp[k - l];
}

3.02 分治解决逆序对数（经典）

long long merge_count(int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) / 2;
    long long res = merge_count(l, mid) + merge_count(mid+1, r);
    vector<int> temp;
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            temp.push_back(a[i++]);
        } else {
            res += (mid - i + 1);
            temp.push_back(a[j++]);
        }
    }
    while (i <= mid) temp.push_back(a[i++]);
    while (j <= r) temp.push_back(a[j++]);
    for (int k = l; k <= r; k++) a[k] = temp[k - l];
    return res;
}

3.03 分治优化动态规划（例：凸包优化、四边形不等式）

这种较复杂，需具体问题具体分析，核心是利用分治减少DP状态转移。

3.04 分治求最近点对

struct Point { int x, y; };
bool cmpX(const Point &a, const Point &b) { return a.x < b.x; }
bool cmpY(const Point &a, const Point &b) { return a.y < b.y; }

double dist(Point a, Point b) {
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double closest_pair(int l, int r, vector<Point> &points) {
    if (r - l + 1 <= 3) {
        double res = 1e18;
        for (int i = l; i <= r; i++)
            for (int j = i + 1; j <= r; j++)
                res = min(res, dist(points[i], points[j]));
        sort(points.begin() + l, points.begin() + r + 1, cmpY);
        return res;
    }
    int mid = (l + r) / 2;
    int midX = points[mid].x;
    double d = min(closest_pair(l, mid, points), closest_pair(mid + 1, r, points));
    inplace_merge(points.begin() + l, points.begin() + mid + 1, points.begin() + r + 1, cmpY);

    vector<Point> strip;
    for (int i = l; i <= r; i++)
        if (abs(points[i].x - midX) < d) strip.push_back(points[i]);
    for (int i = 0; i < (int)strip.size(); i++)
        for (int j = i + 1; j < (int)strip.size() && strip[j].y - strip[i].y < d; j++)
            d = min(d, dist(strip[i], strip[j]));
    return d;
}

四、其他背包问题

1. 分数背包（Fractional Knapsack）【贪心】

特点：物品可以切割，求最大价值。

struct Item {
    double value;
    double weight;
    double ratio() const { return value / weight; }
    bool operator<(const Item &b) const {
        return ratio() > b.ratio();
    }
};

double fractional_knapsack(vector<Item> &items, double W) {
    sort(items.begin(), items.end());
    double res = 0;
    for (auto &item : items) {
        if (W >= item.weight) {
            res += item.value;
            W -= item.weight;
        } else {
            res += item.ratio() * W;
            break;
        }
    }
    return res;
}

2. 分组背包（Grouped Knapsack）

每组只能选一个物品。

const int N = 1005;
int dp[N];
int n, W; // 组数和背包容量

struct Item {
    int w, v;
};
vector<Item> groups[N];

void grouped_knapsack() {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = W; j >= 0; j--) {
            for (auto &item : groups[i]) {
                if (j >= item.w)
                    dp[j] = max(dp[j], dp[j - item.w] + item.v);
            }
        }
    }
}

3. 多维背包（Multi-dimensional Knapsack）

背包有多个容量限制，比如体积和重量都有限制。

const int N = 105;
int dp[N][N]; // 假设两维限制，dp[i][j]

int n;
struct Item {
    int w, vol, val;
};

void multidim_knapsack(vector<Item> &items, int W, int V) {
    memset(dp, 0, sizeof(dp));
    for (auto &item : items) {
        for (int w = W; w >= item.w; w--) {
            for (int v = V; v >= item.vol; v--) {
                dp[w][v] = max(dp[w][v], dp[w - item.w][v - item.vol] + item.val);
            }
        }
    }
}

4. 贪心策略的数学证明要点

• 贪心选择性质：局部最优解可以构成全局最优解。

• 无后效性：一旦做出选择，之后的决策不受影响。

• 交换证明法：假设有最优解与贪心解不同，交换步骤使最优解变成贪心解且不降低价值，达到矛盾。

• 例子：分数背包，按价值/重量比排序，每次取最大比率物品，交换证明确保没有更优解。

五. 哈希相关模板

5.1 STL unordered_map 简单用法

#include <unordered_map>
unordered_map<int, int> mp;

mp[10] = 5;     // 插入或修改
if (mp.count(10)) {
    cout << mp[10] << "\n";
}
mp.erase(10);   // 删除键10

5.2 自定义哈希（防止攻击）

#include <chrono>

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = 
            std::chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

// 使用
unordered_map<long long, int, custom_hash> safe_map;

5.3 哈希字符串（多项式滚动哈希）

const int base = 131;
const int mod = 1e9 + 7;
vector<long long> p, h;

void build_hash(const string &s) {
    int n = (int)s.size();
    p.resize(n + 1);
    h.resize(n + 1);
    p[0] = 1; h[0] = 0;
    for (int i = 1; i <= n; i++) {
        p[i] = (p[i - 1] * base) % mod;
        h[i] = (h[i - 1] * base + s[i - 1]) % mod;
    }
}

long long get_hash(int l, int r) {
    // 1-based index, substring s[l-1..r-1]
    return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
}

5.4 双哈希（防碰撞）模板

const int base1 = 131, mod1 = 1000000007;
const int base2 = 137, mod2 = 1000000009;

struct DoubleHash {
    vector<long long> p1, h1, p2, h2;
    int n;

    DoubleHash(const string &s) {
        n = (int)s.size();
        p1.resize(n + 1); h1.resize(n + 1);
        p2.resize(n + 1); h2.resize(n + 1);
        p1[0] = p2[0] = 1;
        h1[0] = h2[0] = 0;
        for (int i = 1; i <= n; i++) {
            p1[i] = (p1[i - 1] * base1) % mod1;
            p2[i] = (p2[i - 1] * base2) % mod2;
            h1[i] = (h1[i - 1] * base1 + s[i - 1]) % mod1;
            h2[i] = (h2[i - 1] * base2 + s[i - 1]) % mod2;
        }
    }

    pair<long long, long long> getHash(int l, int r) {
        long long x1 = (h1[r] - h1[l - 1] * p1[r - l + 1] % mod1 + mod1) % mod1;
        long long x2 = (h2[r] - h2[l - 1] * p2[r - l + 1] % mod2 + mod2) % mod2;
        return {x1, x2};
    }
};

5.5 滚动哈希（单哈希）模板

const int base = 131;
const int mod = 1000000007;

struct RollingHash {
    vector<long long> p, h;
    int n;

    RollingHash(const string &s) {
        n = (int)s.size();
        p.resize(n + 1);
        h.resize(n + 1);
        p[0] = 1; h[0] = 0;
        for (int i = 1; i <= n; i++) {
            p[i] = (p[i - 1] * base) % mod;
            h[i] = (h[i - 1] * base + s[i - 1]) % mod;
        }
    }

    long long getHash(int l, int r) {
        return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
};

六、常见非背包动态规划问题模板

6.1 最长公共子序列（LCS）

int dp[N][N];
string s1, s2;
int n = (int)s1.size(), m = (int)s2.size();

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (s1[i - 1] == s2[j - 1])
            dp[i][j] = dp[i - 1][j - 1] + 1;
        else
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }
}

6.2 编辑距离（Levenshtein Distance）

int dp[N][N];
string s1, s2;
int n = (int)s1.size(), m = (int)s2.size();

for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
        else dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;
    }
}

6.3 区间DP（矩阵链乘法示例）

int dp[N][N];
int n;
int dims[N]; // 矩阵维度，A_i维度 dims[i-1]xdims[i]

for (int len = 2; len <= n; len++) {
    for (int i = 1; i + len - 1 <= n; i++) {
        int j = i + len - 1;
        dp[i][j] = INT_MAX;
        for (int k = i; k < j; k++) {
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]);
        }
    }
}

6.4 状态压缩DP（旅行商问题TSP）

const int N = 20;
int n;
int dist[N][N];
int dp[1 << N][N];

// 初始化
for (int i = 0; i < (1 << n); i++)
    for (int j = 0; j < n; j++)
        dp[i][j] = INT_MAX;

dp[1][0] = 0; // 从点0开始

for (int s = 1; s < (1 << n); s++) {
    for (int u = 0; u < n; u++) {
        if (!(s & (1 << u))) continue;
        for (int v = 0; v < n; v++) {
            if (s & (1 << v)) continue;
            if (dp[s][u] == INT_MAX) continue;
            dp[s | (1 << v)][v] = min(dp[s | (1 << v)][v], dp[s][u] + dist[u][v]);
        }
    }
}

6.5 树形DP（求树上最大独立集）

vector<int> G[N];
int dp[N][2]; // 0: 不选u, 1: 选u

void dfs(int u, int fa) {
    dp[u][0] = 0; dp[u][1] = 1;
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

6.6 字符串回文子串DP

int dp[N][N];
string s;
int n = (int)s.size();

for (int i = 0; i < n; i++) dp[i][i] = 1;

for (int len = 2; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        if (s[i] == s[j]) {
            if (len == 2) dp[i][j] = 1;
            else dp[i][j] = dp[i + 1][j - 1];
        } else dp[i][j] = 0;
    }
}

七、字符串相关

7.1. Z-Algorithm (Z函数)

vector<int> z_function(const string &s) {
    int n = s.size();
    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    return z;
}

7.2. Rabin-Karp 滚动哈希匹配

const int base = 131;
const long long mod = 1000000007;

long long get_hash(const string &s) {
    long long h = 0;
    for (char c : s) {
        h = (h * base + c) % mod;
    }
    return h;
}

vector<long long> prefix_hash(const string &s) {
    int n = s.size();
    vector<long long> h(n + 1, 0), p(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        h[i] = (h[i - 1] * base + s[i - 1]) % mod;
        p[i] = (p[i - 1] * base) % mod;
    }
    return h;
}

long long get_sub_hash(const vector<long long> &h, const vector<long long> &p, int l, int r) {
    return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
}

7.3. Manacher 算法（最长回文子串 O(n)）

string pre_process(const string &s) {
    string t = "^";
    for (char c : s) t += "#" + string(1, c);
    t += "#$";
    return t;
}

int manacher(const string &s) {
    string t = pre_process(s);
    int n = t.size();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    int max_len = 0;
    for (int i = 1; i < n - 1; i++) {
        int mirror = 2 * center - i;
        if (i < right) p[i] = min(right - i, p[mirror]);
        while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) p[i]++;
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        max_len = max(max_len, p[i]);
    }
    return max_len;
}

7.4. 最长公共子串（DP）

int lcs_length(const string &a, const string &b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                ans = max(ans, dp[i][j]);
            }
        }
    }
    return ans;
}

7.5. Trie 树（字典树）

struct Trie {
    static const int ALPHABET = 26;
    struct Node {
        int next[ALPHABET];
        bool end;
        Node() {
            fill(next, next + ALPHABET, -1);
            end = false;
        }
    };

    vector<Node> trie;
    Trie() { trie.emplace_back(); }

    void insert(const string &s) {
        int node = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (trie[node].next[idx] == -1) {
                trie[node].next[idx] = trie.size();
                trie.emplace_back();
            }
            node = trie[node].next[idx];
        }
        trie[node].end = true;
    }

    bool search(const string &s) {
        int node = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (trie[node].next[idx] == -1) return false;
            node = trie[node].next[idx];
        }
        return trie[node].end;
    }
};

7.6. AC 自动机（多模式匹配）

struct AC_Automaton {
    static const int ALPHABET = 26;
    struct Node {
        int next[ALPHABET];
        int fail;
        bool end;
        Node() {
            fill(next, next + ALPHABET, -1);
            fail = 0;
            end = false;
        }
    };

    vector<Node> trie;
    AC_Automaton() { trie.emplace_back(); }

    void insert(const string &s) {
        int node = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (trie[node].next[idx] == -1) {
                trie[node].next[idx] = trie.size();
                trie.emplace_back();
            }
            node = trie[node].next[idx];
        }
        trie[node].end = true;
    }

    void build() {
        queue<int> q;
        for (int i = 0; i < ALPHABET; i++) {
            int v = trie[0].next[i];
            if (v != -1) {
                trie[v].fail = 0;
                q.push(v);
            } else trie[0].next[i] = 0;
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 0; i < ALPHABET; i++) {
                int v = trie[u].next[i];
                if (v != -1) {
                    trie[v].fail = trie[trie[u].fail].next[i];
                    trie[v].end |= trie[trie[v].fail].end;
                    q.push(v);
                } else {
                    trie[u].next[i] = trie[trie[u].fail].next[i];
                }
            }
        }
    }

    bool query(const string &s) {
        int node = 0;
        for (char c : s) {
            node = trie[node].next[c - 'a'];
            if (trie[node].end) return true;
        }
        return false;
    }
};

7.7. 最小表示法（最小循环移位）

int minimal_rotation(const string &s) {
    string ss = s + s;
    int n = s.size();
    int i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        if (ss[i + k] == ss[j + k]) k++;
        else if (ss[i + k] > ss[j + k]) {
            i = i + k + 1;
            if (i <= j) i = j + 1;
            k = 0;
        } else {
            j = j + k + 1;
            if (j <= i) j = i + 1;
            k = 0;
        }
    }
    return min(i, j);
}

7.7 字符串算法速查表

• 短串匹配：直接 KMP / Z-Function

• 多模式匹配：AC 自动机

• 回文问题：Manacher

• 子串比较：双滚动哈希

• 循环移位问题：最小表示法

• 暴力不可行：考虑哈希 / 后缀数组 / 后缀自动机