1KMP 前缀函数与匹配计数
画出“KMP 前缀函数与匹配计数”的状态或字段，并写出一个关键不变量。
考研计算机 408 全程课 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2无权图最短路
画出“无权图最短路”的状态或字段，并写出一个关键不变量。
3并查集与动态连通
画出“并查集与动态连通”的状态或字段，并写出一个关键不变量。
4归并排序与逆序对
画出“归并排序与逆序对”的状态或字段，并写出一个关键不变量。
第 1 页 · 背面（答案）
BFS 出队顶点 u 时，dist[u] 已是源点到 u 的最少边数；首次发现 v 时设置 dist[v]=dist[u]+1。
前缀函数 pi[i] 是模式串前缀中、同时也是 s[0..i] 后缀的最长真前缀长度；匹配时失配指针沿 pi 链回退。
归并两个有序段时，若右元素小于左元素，则它与左段剩余全部元素构成逆序对。
并查集以父指针森林表示集合；路径压缩缩短查找链，按大小或秩合并避免树退化。