CST PA3
3-2 Not Found
算法构思
注意到 $A$ 的输入长度范围为 $[1, 2^{24}]$, 而可由 $A$ 产生的所有长度为 $n$ 的子串数为 $\vert A\vert - n + 1$. 一个长度为 $n$ 的字符串共有 $2^n$ 种可能, 当 $n = 24$ 时, 由 $\vert A\vert - 24 + 1 < 2^{24}$, $A$ 中已经无法包含所有长度为 $24$ 的子串, 因此第一个未在 $A$ 中出现的子串必是长度不超过 $24$ 的子串.
考虑枚举所有长度为 $k$ 的子串, 其中 $k \le \min(\vert A\vert, 24)$. 对于 $A$ 中长度为 $k$ 的所有子串, 我们依据其二进制值进行标记. 由于数据范围过大, 且实际上需储存的只是串的存在性, 因此考虑使用 Bitmap 对子串情况进行存储.
class Bitmap
// Line 6
// 实现一个 Bitmap 类存储 01 字符串.
class Bitmap {
public:
// 所存放的空间 M[], 容量为 N * sizeof(char) * 8 bit.
unsigned char* M;
int N;
// 初始化 Bitmap, 置 0.
void init(int n) {
N = (n + 7) / 8;
M = new unsigned char[N];
memset(M, 0, N);
}
// 构造函数.
Bitmap(int n = 8) { init(n); }
// 设置 Bitmap 第 k 位为 1.
void set(int k) { M[k >> 3] |= (0x80 >> (k & 0x07)); }
// 清除 Bitmap 第 k 位.
void clear(int k) { M[k >> 3] &= ~ (0x80 >> (k & 0x07)); }
// 检测 Bitmap 第 k 位是否为 1.
bool test(int k) { return M[k >> 3] & (0x80 >> (k & 0x07)); }
// 清零 Bitmap.
void clean() { memset(M, 0, N); }
};void read_input()
在读入初始字符串时, 设置 Bitmap* str, 若初始字符串第 $k$ 位为 $1$, 则使用 str->set[k] 修改 Bitmap 的内容. 将输入字符串从左到右读入 Bitmap* str, 此时 Bitmap* str 存放了一个 $01$ 字符串.
// Line 32
void read_input(Bitmap* str, char& input, int& len) {
while(input != '\n'){
input = getchar();
if(input == '1')
str->set(len);
len++;
}
}int read()
// Line 42
int read(Bitmap* bitmap, int pos, int read_len) {
int tmp = 0;
for (int i = 0; i <= read_len - 1; i++)
tmp = bitmap->test(pos + i) ? (tmp << 1) + 1 : tmp << 1;
return tmp;
}read() 从 Bitmap* str 第 pos 位开始读取为长 read_len 的二进制串, 并将其转换为十进制数. 为了节省遍历子串的时间, 首先考虑 $k = \min(\vert A\vert, 24)$ 的情形.
...
// Line 113
int k = search_len;
Bitmap* a = new Bitmap(1 << search_len);
Bitmap* b = new Bitmap(1 << (search_len - 1));
...Bitmap* a 用于存储所有长 $k$ 位的 $01$ 串在原字符串中的出现情况, 若 a->test(i) == true, 则输入串中存在十进制值为 $i$ 的 $k$ 位 $01$ 二进制串. Bitmap* b 用于存储所有长 $k - 1$ 位的 $01$ 串在原字符串中的出现情况, 若 b->test(j) == true, 则输入串中存在十进制值为 $j$ 的 $k - 1$ 位 $01$ 二进制串.
从 Bitmap* str 的末尾开始向头部遍历, 对于当前处理的二进制串的十进制值 $s = \overline{a_{m + 1}a_{m + 2}\cdots a_{m + k}}_2$, 下一个处理串的十进制值 $s’ = \overline{a_ma_{m + 1}\cdots a_{m + k - 1}}_2 = a\gg 1 + a_m\ll (k - 1)$.
从后向前遍历, 节省了将二进制串转换为十进制串的时间.
...
// Line 118
int pos = len - k;
int get = read(str, pos, k);
a->set(get);
b->set(get >>= 1);
while (--pos >= 0) {
if (str->test(pos))
get += 1 << (k - 1);
a->set(get);
b->set(get >>= 1);
}
set_end(str, b, len - k, k);
...为此, 首先读入 str 末端的 $k$ 长子串 get, 调用 a->set(get) 将其存储在 Bitmap* a 中, 并使用一个 while 循环遍历接下来所有 $k$ 长子串.
void set_end()
// Line 68
void set_end (Bitmap* str, Bitmap* a, int pos, int k) {
a->set(read(str, pos + 1, k - 1));
}调用 set_end() 将 str 末尾的 $k - 1$ 位 $01$ 子串加入 Bitmap* b.
考虑到长度为 $k - 1$ 的子串. 对于所有 $k$ 长子串的十进制值 $S_1, S_2, \cdots, S_{\vert A\vert - k + 1}$, 长度为 $k - 1$ 的子串恰为所有 $k$ 长子串删去最后一位, 再补上 str 中末端的 $k - 1$ 长子串, 其十进制值 $R_1 = S_1\gg 1, R_2 = S_2\gg 1, \cdots, R_{\vert A\vert - k + 1} = S_{\vert A\vert - k + 1}\gg 1, R_{\vert A\vert - k + 2}$, 其中 $R_{\vert A\vert - k + 2}$ 调用 set_end(str, b, len - k, k) 来设置.
接下来调用 check_full(b, k) 检查 Bitmap* b 中是否已经存储了所有 $k - 1$ 长子串.
void get_ans()
// Line 82
void get_ans (Bitmap* a, int k, int& output, int& precision) {
for (int i = 0; i < (1 << k); i++)
if (!a->test(i)) {
output = i;
precision = k;
break;
}
}若所有 $k - 1$ 长子串都已经存储在了 Bitmap* b 中, 那么说明 str 中首个未出现的字符串长度为 $k$, 只需调用 get_ans(a, k, output, precision) 在 Bitmap* a 中遍历寻找首个未出现的 $k$ 长子串, 并调用 show_ans(output, precision) 输出在原串中未出现的最短且字典序最小的 $k$ 长子串即可.
void trans()
// Line 54
void trans (Bitmap* a, Bitmap* b, int k) {
for (int i = 0; i < (1 << k); i++)
if (a->test(i))
b->set(i >> 1);
}否则, 若存在 $k - 1$ 长子串未存储在 Bitmap* b 中, 那么调用 copy(a, b) 将 Bitmap* b 的值赋给 Bitmap* a, k 自减, 并调用 b->clean() 将 Bitmap* b 置零. 此时 Bitmap* a 存储了所有 $k$ 长子串, 并调用 trans(a, b, k) 利用其中值更新 Bitmap* b 中的 $k - 1$ 长子串, 仍然需要使用 set_end(str, b, len - k, k) 将 str 末端的子串加入 b.
当遍历到长度为 $k - 1$ 的串全部存在, 而 $k$ 长子串存在缺失时, 将 $k$ 长子串所缺少十进制值对应的首个 $01$ 子串输出.
复杂度估计
时间复杂度
第一次读入串 str 的时间复杂度为 $O(\vert A\vert)$;
对于子串的处理考虑极端情况, 对 $k$ 长子串存储、遍历枚举、更新所需要时间为 $O(2^k)$, 若从长 $24$ 子串遍历至长 $1$ 子串, 消耗时间为 $O(2^{25})$.
综上, 算法最坏时间复杂度为 $O(\vert A\vert + 2^{25})$.
空间复杂度
空间复杂度主要来自于使用了 Bitmap 存储目的串的过程.
最坏情况下开辟了两个可存储 $2^{24}$ bit, 一个可存储 $2^{23}$ bit 的 Bitmap, 最坏情况空间复杂度为: $(2\times 2^{24} + 2^{23}) bit = 5\times 2^{20} B = 5MB$, 在题目要求范围内.
