Sgu/142

//by hza
#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
 
const int MAX=500000+10;
int n,len;
char a[MAX];
bool tree[MAX*10];
int now;
int answer,ans[1000],node;
int total;
 
int main()
{
	scanf("%d",&n);
	len=ceil(log(n)/log(2));
	if(len<=n)++len;
	total=1<<(len+1);
	scanf("%s",a);
	int i,j;
	for(i=0;i<n;++i)
	{
		now=1;
		for(j=0;j<len&&i+j<n;++j)
		{
			if(a[i+j]=='a')
				now=now*2;
			else
				now=now*2+1;
			tree[now]=1;
		}
	}
	for(now=2;now<total;++now)
	{
		if(!tree[now])
			break;
	}
	int t;
	answer=floor(log(now)/log(2));
	while(now>1)
	{
		t=floor(log(now)/log(2));
		ans[ t ]=now&1;
		now>>=1;
	}
	printf("%d\n",answer);
	for(i=1;i<=answer;++i)
		printf("%c",ans[i]+'a');
	printf("\n");
}

分析：http://www.cnblogs.com/keam37/p/3840375.html

//by keambar
#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');
}