关于后缀自动机的定义
  • 板块学术版
  • 楼主Emptilife
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/11/5 22:14
  • 上次更新2023/11/5 22:38:48
查看原帖
关于后缀自动机的定义
996129
Emptilife楼主2023/11/5 22:14

oi-wiki 原文如下:

字符串 s 的 SAM 是一个接受 s 的所有后缀的最小 DFA(确定性有限自动机或确定性有限状态自动机)。

求助,为什么 SAM 是“能接受 s 的所有后缀的自动机”而不是接受所有子串?直接一条链不也能接受所有后缀,而且比 SAM 更小吗?

2023/11/5 22:14
加载中...