名称：后缀结构构建器 描述：构建和查询后缀数组及相关结构 允许使用的工具：
- 读取
- 写入
- 搜索
- 全局匹配
- 编辑
后缀结构构建器技能
目的
使用高效的构建算法和常见查询实现来构建后缀数组、后缀树及相关结构。
能力
- 后缀数组构建（SA-IS，DC3）
- LCP数组构建
- 后缀树构建
- 后缀自动机构建
- 每种结构的查询实现
- 用于LCP查询的稀疏表
目标流程
- 字典树-后缀结构
- 模式匹配算法
- 字符串处理
后缀结构
后缀数组
- O(n log n) 或 O(n) 构建
- 结合LCP实现强大查询
- O(m log n) 模式匹配
LCP数组
- Kasai算法 O(n)
- 用于LCA的区间最小值查询
- 不同子串计数
后缀树
- Ukkonen算法 O(n)
- 更复杂但功能强大
- 直接模式匹配 O(m)
后缀自动机
- O(n) 构建
- 所有子串的最小自动机
- 适用于计数问题
输入模式
{
"type": "object",
"properties": {
"structure": {
"type": "string",
"enum": ["suffixArray", "lcpArray", "suffixTree", "suffixAutomaton"]
},
"algorithm": { "type": "string" },
"queries": { "type": "array" },
"language": {
"type": "string",
"enum": ["cpp", "python", "java"]
}
},
"required": ["structure"]
}
输出模式
{
"type": "object",
"properties": {
"success": { "type": "boolean" },
"code": { "type": "string" },
"complexity": { "type": "object" },
"queryImplementations": { "type": "array" }
},
"required": ["success", "code"]
}