§04 串

Sunday 匹配

BM 的简化变体：失配时看对齐区间后的下一个字符，按偏移表大步跳跃——平均 O(n)，实践中比 KMP 更快。

Sunday 匹配

第 01 / 15 步

文本 "HERE IS A SIMPLE EXAMPLE"，模式 "EXAMPLE"。偏移表已构建：每个字符记录其在模式中最右出现位置（从右数）。比较 0 · 交换 0

伪代码


				
					
					1
					// Sunday 匹配
				
			
				
					
					2
					构建偏移表 offset[c] = 字符 c 在模式中最右出现位置（从右数）
				
			
				
					
					3
					i = 0
				
			
				
					
					4
					while i + |P| <= |T|:
				
			
				
					
					5
					  j = 0..|P|-1 逐位比较 T[i+j] 与 P[j]
				
			
				
					
					6
					  if 全部匹配: 命中于 i
				
			
				
					
					7
					  else: c = T[i + |P|]
				
			
				
					
					8
					    i += offset[c] ?? |P| + 1   // 大步跳跃

01 / 15

速度