算法可视化
入门执行逻辑
KMP:字符串匹配
主串和模式串对齐比较,失配时不回退主串,而是利用 next 数组让模式串跳到合适位置,效率 O(n+m)。
main.cpp第 1 行
1// KMP: 失配时利用 next 数组跳过, 主串不回退
2while (i < n && j < m) {
3 if (j == -1 || s[i] == p[j]) { i++; j++; }
4 else j = next[j]; // 失配: 模式串回退
5}
6// 匹配成功: 起始位置 i - m = 3
变量表3 个变量
i0
j0
next[-1, 0, 0, 0, 1, 2]
字符串对齐(蓝色 = 当前比较位置)
主串
ABCABCABD
模式
ABCABD
1/13
主串 "ABCABCABD",模式串 "ABCABD",next 数组 = [-1, 0, 0, 0, 1, 2]。开始对齐比较
1 / 13