codeoforces 271 D (后缀自动机 SAM) - c++编程基础

t(que,0,sizeof(que));
root=tail=&que[tot++];
}
void solve(int limit)
{
int i,j;
memset(c,0,sizeof(c));
for(i=0;i c[que[i].val]++;
for(i=1;i c[i]+=c[i-1];
for(i=0;i top[--c[que[i].val]]=&que[i];
int sum=0;
for(i=1;i {
node *p=top[i];
if(p->par->sum>limit)
{
p->sum=limit+1;
continue;
}
int mi=p->par->val+1,ma=p->val,tmp=p->par->sum,po=p->po;
for(j=mi;j<=ma;j++)
{
if(vis[str[po-j+1]-'a'])
{
tmp++;
if(tmp>limit)
{

break;
}
else
sum++;
}
else
sum++;
}
p->sum=tmp;
}
printf("%d\n",sum);
}
int main()
{
//freopen("dd.txt","r",stdin);
scanf("%s",str);
int i,k,l=strlen(str);
init();
for(i=0;i {
add(str[i]-'a',len++,i);
}
char tmp[26];
scanf("%s",tmp);
for(i=0;i<26;i++)
vis[i]=1-(tmp[i]-'0');
scanf("%d",&k);
solve(k);
return 0;
}

codeoforces 271 D (后缀自动机 SAM) (二)