SGU142 解题手记
　　原串不超过500000位，所以肯定有一个19位的串不是原串的子串，因为19位的串有2^19=524288种，而原串的19位子串数目只有499972个。
　　这样只需要统计原串的1至19位的子串就行了。
　　Submit 1: RTE on 11。把min(mask[k]+1,n)写成max了。
　　Submit 2: WA on 1。根本不该写出min(mask[k]+1,n)来，统计原串的k位子串跟k位串共有多少种没有关系。
　　Submit 3: AC。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <algorithm>
#include <cstdio>
using namespace std;
 
int main()
{
    int mask[20];
    for (int i=0;i<20;i++) mask[i]=(1<<i)-1;
    bool str[500000],substr[524288],find;
    int n;
    char c;
    scanf("%d\n",&n);
    for (int i(0);i<n;i++)
    {
        scanf("%c",&c); str[i]=(c=='b');
    }
    for (int k=1;k<20;k++)
    {
        find=false;
        fill(substr,substr+mask[k],false);
        int s=0;
        for (int i(0);i<k-1;i++) s=(s<<1)|str[i];
        for (int i=k-1;i<n;i++) substr[s=(s<<1)&mask[k]|str[i]]=true;
        for (int i=0;i<=mask[k];i++)
            if (!substr[i])
            {
                printf("%d\n",k);
                for (int j=k-1;j>=0;j--)
                    if (i>>j&1) printf("b");
                    else printf("a");
                find=true;
                break;
            }
        if (find) break;
    }
    return 0;
}