时间限制：0.5s

空间限制：16M

题意

      给出一个仅由‘a‘，‘b’组成的字符串S，长度小于500 000，求一个由‘a’，‘b’组成的不是S子串的字符串T。

      输出T的长度和T。

Sample Input

11aabaaabbbab

Sample Output

4aaaa

Solution：

             从字符串长度上看,我们需要一个O(n)的算法.

             考虑串T的最大长度,在什么范围

             长度为k的串,有2^k个,占了k*2^k位,即1*2+2*2^k,+....+p*2^P<=500 000;

             可知串T的长度是小于log₂(500000)<19,的.

             因此只要从S串的开始,每一位往后最多枚举19位,就能筛选出所有有用的子串.

             如果用 1 0 分别代表‘a‘,‘b‘ ;

             那么可以用一个二进制长为19位的数代表这个串.

             只需要开一个f[length][key]的数组(length<=19,key<=2¹⁹),注意到内存只有16M,因此,这个二维数组的类型必须是bool型,不然将超出内存限制.

             最后从数组中找到最短的那个没有出现过的串,输出即可.

             时间复杂度正是O(n),满足我们的需要的.

参考代码

#include <cstdio>#include <cmath>char ch;int g[1 << 19];bool f[20][1 << 19];int k, n, len, fid;int main() {	scanf ("%d", &n);	ch = getchar();	for (int i = 1; i <= n; i++)		g[i] = (ch=getchar() == ‘a‘);	for (int i = 1; i <= n; i++) {		k = 0;		for (int j = 0; j <= 18; j++) {			if (i + j <= n) {				k = k << 1 | g[i + j];				f[j + 1][k] = 1;			}			else break;		}	}	for (len = 1; len <= 19; len++) {		for (k = 0; k < (1<<len); k++)			if (!f[len][k]) {				fid = 1;				break;			}		if (fid) break;	}	printf ("%d\n", len);	for (int i = len - 1; i >= 0; i--)		printf ("%c", k & (1 << i) ? ‘a‘ : ‘b‘);}