Leetcode-214 ​

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1： 输入： s = "aacecaaa" 输出： "aaacecaaa"

示例 2： 输入： s = "abcd" 输出： "dcbabcd"

提示：

• 0 <= s.length <= 5 * 104
• s 仅由小写英文字母组成

看到回文串第一反应是马拉车或者dp。

但是认真思考样例 ——

在示例一中，我们添加的前缀是"a"，恰好是"aacecaa"这个最长回文前缀去掉之后的部分再进行一个反转。 示例二同理

仔细一想确乎是这样 ——

• 把整个原串反转后拼接，一定是回文串
• 如果前缀是回文的，那么不需要考虑

所以把原问题转化成“找 s 的最长回文前缀”

那么这又想到马拉车了 —— 跑马拉车的时候维护一下可以触碰到最左侧的回文串的长度，找到最长的即可

于是可以有第一种解法。

但是又看到了找”前缀“这件事情，所以不妨看看KMP能不能解 ——

先明确KMP维护的pi[i]表示P[0...i]中最长的相同的前后缀，所以就要寻找最长回文前缀的问题化归成最长相同前后缀问题 ——

“把回文串沿着中心劈开，把前一半反转一下就和后一半一致”

想到构造 ——

combine = s + "#" + reverse(s)

直接看例子

a a c e c a a a # a a a c e c a a
^

Job System ​

把一些可以并行执行的 CPU 工作交给 Worker 去做，比如资产加载、可见性计算、后台统计等。

核心思想 ——

业务模块决定要做什么
JobSystem 只决定什么时候做、在哪个线程做、做完以后如何通知

也就是说，AssetManager 负责加载什么资产，Renderer 负责哪些渲染数据可以并行处理，而 JobSystem 本身不理解 Asset，也不理解 Renderer。

它只是一个调度器。

模块边界 ​

ChikaProfiler
    ↑
ChikaJobs
    ↑
    ├───────────────┐
    │               │
ChikaAsset      ChikaRender
    ↑               ↑
    └───────┬───────┘
            │
      EngineContext

ChikaJobs 只依赖 ChikaProfiler，不依赖 Asset 和 Render。

这样设计是为了让 JobSystem 保持干净：

• JobSystem 只理解 callable、Handle、队列和完成状态
• AssetManager 决定加载什么，JobSystem 只负责找 Worker 执行
• Renderer 决定哪些渲染数据能并行，JobSystem 不理解 RenderWorld
• Profiler 只接收事件，不反过来控制 JobSystem

简述 ​

假设现在 AssetManager 想异步加载一个 Shader。

最简单的做法可能是直接开一个线程：

std::thread([path]
{
    LoadShader(path);
}).detach();

这看起来很方便，但问题非常多：

1. 线程数量不可控
2. 任务失败不好收集
3. 不知道什么时候完成
4. 关闭引擎时不好等待
5. Profiler 不知道任务在哪里跑
6. 多个模块都自己开线程，最后整套引擎会变成面条（

所以引入 JobSystem。

上层不直接创建线程，而是提交一个任务：

JobHandle handle = jobs.Schedule("Asset.LoadShader", []
{
    LoadShader();
});

JobSystem 内部负责：

• 把任务放进队列
• 唤醒 Worker
• 执行 callable
• 记录状态
• 捕获异常
• 通知等待者
• 在关闭引擎时统一收尾

这样业务层只关心“我要做什么”，不关心“线程怎么调度”。

总体数据流向 ​

外部模块 / 主线程
        │
        ▼
    Schedule Job
        │
        ▼
  JobStorage 分配 Slot
        │
        ▼
  放入可执行队列
        │
        ▼
    Worker 取任务
        │
        ▼
    执行 callable
        │
        ▼
  Completed / Failed / Cancelled
        │
        ▼
  Wait / Release / Detach

简单来说 ——

1. 外部模块提交任务
2. JobSystem 给任务分配一个内部位置
3. 任务进入队列
4. Worker 从队列中取出任务
5. Worker 执行任务
6. 调用方等待或放手不管
7. JobSystem 最后回收任务位置

结构分析 ​

JobSystem 可以粗略分为五块：

|部分|作用| |