给出一个长度为N的串S(N≤500000)。这个串只包含“a”“b”两种字母。
找一个长度为L的串T也是右“a”“b”两种字母组成使得该串不是串S的
子串且长度L尽可能小。
问题分析
这是一道统计的题目。由于串只由两种字母组成因此相当于一个01串。
如果我们求出S的所有子串然后标记起来再由小到大枚举T串直到T串
不是S的子串那么就能得出解了。然而S的子串是十分多的所以我们有必
要分析一下这道题的特征。
题目要我们使长度L尽可能小。而对于某一个L串S中最多包含N-L+1
个长度为L的子串。而长度为L的串一共有2L个。若N-L+1<2L则必有某个长
度为L的串T不是S的子串。而N≤500000因此N-19+1<219所以无论如何L=19必定是一个可行的L。因此我们只需对长度不超过19的子串进行统计。题
目的规模就大大减小了。
先将S转成用01串表示。并建立一个Mark数组统计所有长度为1~19的
串是否是S的子串。对于S的第i位它单独可以构成一个长度为1的子串Q1
我们把Mark[1,f(Q1)]置为True。它和第i+1位可以构成一个长度为2的子串Q2我们把Mark[2,f(Q2)]置为True。如此下去只需一直处理到第i位和它后面的18位构成一个长度为19的串Q19我们把Mark[19,f(Q19)]置为True。其中f(Qk)表示01串Qk所对应的十进制数。 这样对于每一位都只是处理19次。时间复杂度是O(N)的。而每一位i只与
它后面的18位发生联系因此存储上可以只开一个1..19的数组空间复杂度是
O(Log2N)的。
处理完每一位之后我们就可以由小到大枚举串T如果发现它的Mark是
False的表示它不是S的子串可以直接输出解。
#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<algorithm>
#include<set>
#include<vector>
#define LL long long
#define inf 0x7fffffff
#define E 1e-9
#define M 2520
#define N 500005
using namespace std;
int n,k,t;
bool ma[20][524288];
bool a[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("ex.in","r",stdin);
#endif
scanf("%d%*c",&n);
for(int i=0;i<n;i++)
{
char c;
scanf("%c",&c);
a[i]=c=='a'?0:1;
}
for (int i=0;i<n;++i )
{
int x=0;
for(int j=i;j<n&&j<i+19;j++)
{
x=x*2+a[j];
ma[j-i+1][x]=1;
}
}
int flag=1,x,num;
for(int i=1;i<20&&flag;i++)
{
for(int j=0;j<(1<<i);j++)
{
if(!ma[i][j])
{
num=i;
x=j;
flag=0;
break;
}
}
}
printf("%d\n",num);
char str[20];
int i=0;
while(x)
{
str[i++]=x%2;
x/=2;
}
for(int j=0;j<num-i;j++)
printf("a");
for(i--;i>=0;i--)
printf("%c",str[i]==1?'b':'a');
return 0;
}