一、题目大意

给定一个长度为\(n\)的\(01\)串\(A\)，寻找最短的不是\(A\)的子串的\(01\)串\(B\)并输出，如有多个则输出字典序最小的。

其中\(1 \leq n \leq 16777216\)。

二、算法分析

本题中，由于空间限制为\(6\)MB，若采用string类型输入字符串，最大需要\(\displaystyle \frac{16777216}{1024 \times 1024}=16\)MB的空间进行存储，显然会造成空间超限的问题。于是考虑更节省空间的存储方式——位图。使用位图存储方式，由于每个char类型变量中都有\(8\)个bit，则可以将存储空间缩小为原来的\(\frac{1}{8}\)，足以通过本题。

下面是如何寻找答案的问题。设子串长度为\(x\)，则不同的\(01\)串一共有\(2^x\)种，而字符串中最多有\(n-x+1\)个长度为\(x\)的子串。因此只要子串长度\(x\)满足\(2^x>n-x+1\)恒成立，则一定可以找到答案。注意到以下这个显然的事实：

而当\(x=24,n=2^{24}\)时，上述不等式成立，则答案字符串的长度\(l\)一定满足\(1\leq l \leq 24\)。因此我们可以直接枚举这\(24\)个长度，一一检查即可。

对\(1 \leq l \leq 24\)的每个长度\(l\)，输入的字符串已经被存储在位图s中，我们可以构建一个空位图t，之后遍历位图s中所有长度为\(l\)的子串，设每个\(01\)子串对应的十进制表示为\(k\)，将位图t中的第\(k\)位赋值\(1\)。遍历完成后，寻找位图t中第一个值为\(0\)的位，若能找到，位数的二进制表示（需要补零达到相应长度）的字符串便是答案。

三、代码实现

本题中最核心的部分就是手动实现一个位图，实现快速清空某一长度对应的字节内存，将位图中某一位赋值\(1\)，以及获取位图中某一位的值。为此，使用结构体实现位图，并且合理使用位运算以实现功能。 

const int N = 16777216 + 100;
struct BitMap {
    char n[N / 8];
    void emptyed(int len) {
        memset(n, 0, (len + 7) / 8);
    }//清空len长度的byte，向上取整

    void set_1(int p) {
        n[p >> 3] |= 1 << (p & 7);
    }//把第p位设为1

    int val(int p) {
        return n[p >> 3] >> (p & 7) & 1;
    }//获取第p位的值
};

接下来便是检查是否存在长度为\(len\)的子串。为此我们定义check()函数，传入参数len和字符串的总长度tot_len（也即位图\(s\)用于存储输入字符串的总长度）。我们首先获得位图s中前\(len\)位\(01\)串对应的十进制表示temp，并将位图t的第temp位设置为\(1\)： 

int temp = 0;
for(int j = 0; j < len; j ++) {
    temp |= s.val(j) << (len - 1 - j);
}
t.set_1(temp);

接着向后推进的过程中，每推进一位，则将temp的最高位设置为\(0\)，整体左移一位，再加上新进入的一位数据即可。递推过程如下： 

for(int i = 1; i <= tot_len - len; i ++) {
    temp &= ~(1 << len - 1);
    temp = temp << 1;
    temp |= s.val(i + len - 1);
    t.set_1(temp);
}

之后遍历位图t，返回第一个不是\(0\)的元素对应的位数；若找不到，返回\(-1\)。

为了能按位输出一个十进制数的二进制表示，同时控制输出长度，为此手动定义output()函数： 

void output(int x,int len) {
for(int i = len - 1; ~i; i --)
    cout << (x >> i & 1);
}//输出二进制每一位

这样就可以输出\(x\)的二进制表示的后\(len\)位。

在输入处理时，由于空间限制，我们需要一个字符一个字符地输出，并且记录输入的总长度，于是可以考虑使用getchar()函数进行输入： 

char c;
int num = 0;
while((c = getchar()) == '0' || c == '1') {
    if(c == '1') {
        s.set_1(num);
    }
    num ++;
}

最后就是枚举长度\(len\)，每次枚举之后调用位图的emptyed()方法将\(len\)长度对应的Byte全都清空（向上取整），找到答案后输出即可。 

for(int k = 1; k <= 24; k ++) {
    int res = check(k, num);
    t.emptyed(1 << k);
    if(res != -1) {
        output(res, k);
        break;
    }
}

四、实现中值得注意的细节

  1. 要熟记位运算符与普通四则运算符之间的优先级关系，避免在实现时出现运算错误。

  2. 最开始，我没有将两个位图s和t定义为全局变量，而是在main()函数中定义，这导致了栈空间分配不足，终端调试时甚至无法输入数据。因此还是尽量定义全局变量为好。

五、时间及空间复杂度分析

  1. 本题中，对\(1 \leq l \leq 24\)的每个长度\(l\)，分别对位图s和t进行了遍历，则时间复杂度为\(O(n)\)（常数略大）。

  2. 本题中，主要在构造位图时申请了空间，空间复杂度为\(\displaystyle O\left(\frac{n}{4} \right)\)。