4.2 综合题：找出所有重叠匹配并证明线性复杂度

任务：返回模式在主串中的所有 0 基起点，允许重叠。先构造前缀函数，再扫描主串；完整匹配后不能把 j 清零，而应回退到 pi[m-1]，保留可作为下一个匹配开头的后缀。

vector<int> find_all(const string&t,const string&p){
 vector<int> ans;if(p.empty())return ans;
 vector<int> pi=prefix(p);int j=0;
 for(int i=0;i<(int)t.size();++i){
  while(j>0&&t[i]!=p[j])j=pi[j-1];
  if(t[i]==p[j])++j;
  if(j==(int)p.size()){
   ans.push_back(i-j+1);
   j=pi[j-1];
  }
 }
 return ans;
}

手工推演 T='aaaaa'、P='aaa'，pi=[0,1,2]。读到下标 2 首次匹配，记录 0 后 j 回到 2；读下标 3 立即再次完成，记录 1；读下标 4 记录 2。若成功后清零，只会找到起点 0，漏掉重叠结果。

正确性依据：状态 j 始终是当前已扫描主串前缀的后缀，与模式前缀相等的最大长度。失配沿失败链接枚举更短可行边界，不会跳过候选；成功时长度达到 $m$，起点必为 i-m+1。

复杂度证明不能只说有一个 for。扫描中 j 每增加一次由字符匹配造成；回退总量不会无限超过此前增长的累计量，因此主循环总比较为线性量级，加预处理得 $O(n+m)$，空间 $O(m+k)$，其中 $k$ 是答案个数。

错解反馈：空模式直接访问 p[0] 会越界；匹配后不回退会使下一轮 p[j] 越界；返回结束下标而非起点；用集合去重掩盖算法重复输出，均未处理状态本身。

迁移题：T='abababa'、P='aba' 的所有起点是什么？答案 [0,2,4]。独立验收：严格编译运行空文本、模式长于文本、无匹配、单匹配、重叠匹配五类用例，并手写每步 i,j。