考虑 dp[i] 为 右端点为 i 处 的所有子串包含 bessie的答案总和
最后的答案为
考虑如何计算 dp[i]
加入 从 i 往前找到最近的一个 ,使得 恰好包含了一个 bessie子序列,那么 ,因此右端点从j处拉到i处,原来包含的bessie依然被包含,而对于右端点 , 当左端点落在 时,会额外多包含刚刚发现的一个bessie子序列。
考虑对于dp[i] 如何找到 对应的j,
表示从 i 处往前看 最近的 在什么位置
表示从 i 处往前看 最近的 子序列起始在什么位置
表示从 i 处往前看 最近的 子序列起始在什么位置
表示从 i 处往前看 最近的 子序列起始在什么位置
表示从 i 处往前看 最近的 子序列起始在什么位置
表示从 i 处往前看 最近的 子序列起始在什么位置
显然当
当 时,
当 时,
当 时,
当 时,
当 时,
当 时,