线性 space 支持静态字符串子序列查询的数据结构
Linear space data-structure supporing subsequence query on a static string
从长度为 n 的给定字符串 S 构建数据结构，支持快速查询以检查输入字符串是否 [=长度为 m 的 59=]J 是 S.
的子序列
S 是一个静态字符串，数据结构的预处理时间可以忽略不计。
要求：
- space消耗应该是线性的
O(n)
subsequence(J) 的运行时间应该取决于 m - 不一定 O(m) 但越快越好。
什么是子序列？
A 是 B 的子序列，如果 A 可以通过删除零或来自 B 的更多字符。即 ABA 是 ADBDBAC
的子序列
我试过的
支持Subsequence(J)查询的数据结构存储从S中的每个字母到S[=109=中的下一个字母的指针] 字母表中的每个字母。
设A 为长度为n + 1 的数组。 A 包含散列-tables 在字母表上散列，σ。 hash-table 中的每个键值对 (k,v) 包含一些字母 k 作为键，它的下一次出现为值 v.
散列-tableA_0包含字母表中每个字母的第一次出现。
散列-table A_1 包含字母在 [= 处第二次出现的索引160=] 以及其他字母的第一次出现。
散列-table A_2 包含字母 [=162 第二次出现的索引=] 和 S_2 假设它们是不同的字母 - 否则 A_2 将包含第三个索引S_1 处的字母 - 以及其他字母的第一次出现等等...
例子：如果T是B C A D F B，¥表示hashtable A_0 并表示一个 Ø 空指针，数据结构如下所示：
|0 1 2 3 4 5
|¥ B C A D B
A|3 3 3 Ø Ø Ø
B|1 5 5 5 5 Ø
C|2 2 Ø Ø Ø Ø
D|4 4 4 4 Ø Ø
字母表 \sigma 由 T 中的字母组成，是静态的。因此，可以使用完美哈希（FKS）。
运行查询
要使用字符串 J 执行 Subsequence(J) 查询，我们查找第一次出现的 A-索引 J_0 在 S 中使用 A_0.
在示例中，我们可以查询 Subsequence("BAB") 来测试 BAB 是否是一个子序列：
* 在第 0 列 returns 索引 1 中查找 B
* 在第 1 列 returns 索引 3 中查找 A
* 在第 3 列中查找 B，其中 returns 索引 5
只要我们不传递空指针，字符串就是子序列。哈希查找需要固定时间，我们最多只能执行 |J| 次，运行时间为 O(|J|).
space消耗O(|J|·|S|)
检查J是否是S的子序列的简单而缓慢的方法是：
- 从S开头开始
- 对于J中的每个字符c，按顺序，在S中向前移动到c.
的下一次出现
- 如果你走到最后并找到每个字符的匹配项，那么 J 是 S 的子序列。
您可以通过构建从 S 中出现的每个字符到该字符出现位置的排序数组的映射来加速这些搜索。
然后，要在步骤 (2) 中查找下一个字符，您可以查找该字符的位置数组，并在数组中进行二分查找以查找当前位置之后的下一个字符。
进行子序列检查的最坏情况总复杂度为 O(m log n).
从长度为 n 的给定字符串 S 构建数据结构，支持快速查询以检查输入字符串是否 [=长度为 m 的 59=]J 是 S.
的子序列S 是一个静态字符串，数据结构的预处理时间可以忽略不计。
要求：
- space消耗应该是线性的
O(n) subsequence(J)的运行时间应该取决于 m - 不一定O(m)但越快越好。
什么是子序列？
A 是 B 的子序列，如果 A 可以通过删除零或来自 B 的更多字符。即 ABA 是 ADBDBAC
我试过的
支持Subsequence(J)查询的数据结构存储从S中的每个字母到S[=109=中的下一个字母的指针] 字母表中的每个字母。
设A 为长度为n + 1 的数组。 A 包含散列-tables 在字母表上散列，σ。 hash-table 中的每个键值对 (k,v) 包含一些字母 k 作为键，它的下一次出现为值 v.
散列-tableA_0包含字母表中每个字母的第一次出现。
散列-table A_1 包含字母在 [= 处第二次出现的索引160=] 以及其他字母的第一次出现。
散列-table A_2 包含字母 [=162 第二次出现的索引=] 和 S_2 假设它们是不同的字母 - 否则 A_2 将包含第三个索引S_1 处的字母 - 以及其他字母的第一次出现等等...
例子：如果T是B C A D F B，¥表示hashtable A_0 并表示一个 Ø 空指针，数据结构如下所示：
|0 1 2 3 4 5
|¥ B C A D B
A|3 3 3 Ø Ø Ø
B|1 5 5 5 5 Ø
C|2 2 Ø Ø Ø Ø
D|4 4 4 4 Ø Ø
字母表 \sigma 由 T 中的字母组成，是静态的。因此，可以使用完美哈希（FKS）。
运行查询要使用字符串 J 执行 Subsequence(J) 查询，我们查找第一次出现的 A-索引 J_0 在 S 中使用 A_0.
在示例中，我们可以查询 Subsequence("BAB") 来测试 BAB 是否是一个子序列：
* 在第 0 列 returns 索引 1 中查找 B
* 在第 1 列 returns 索引 3 中查找 A
* 在第 3 列中查找 B，其中 returns 索引 5
只要我们不传递空指针，字符串就是子序列。哈希查找需要固定时间，我们最多只能执行 |J| 次，运行时间为 O(|J|).
space消耗O(|J|·|S|)
检查J是否是S的子序列的简单而缓慢的方法是：
- 从S开头开始
- 对于J中的每个字符c，按顺序，在S中向前移动到c. 的下一次出现
- 如果你走到最后并找到每个字符的匹配项，那么 J 是 S 的子序列。
您可以通过构建从 S 中出现的每个字符到该字符出现位置的排序数组的映射来加速这些搜索。
然后，要在步骤 (2) 中查找下一个字符，您可以查找该字符的位置数组，并在数组中进行二分查找以查找当前位置之后的下一个字符。
进行子序列检查的最坏情况总复杂度为 O(m log n).