bzoj2534 L-gap字符串 [SAM] [线段树] [启发式合并]

题意

bzoj2534

给你一个字符串 $S$,以及一个 $L$。 求 $S$ 中有多少个形如 $uvu$ 的子串,其中 $u$ 非空,且 $v$ 的长度恰好为 $L$。

其中 $len(S) \leqslant 50000$ ,$L \leqslant 10$。

分析

讲道理数据里面居然全是大写字母

总感觉自己YY出来了什么神奇的东西,网上好像用 $SA$ 的比较多。

看到字符串第一个想 $SAM$ (被我校 $SAM$ 之神兔子教坏了)

考虑对于一个某个点 $now$ 的 $right$ 集合中的一个元素 $k$ ,它所能产生的贡献是在区间 $[k-L-mx[now],k-L-1]$ 或者 $[k+L+1,k+L+mx[now]]$ 并且在这个点的 $right$ 的集合中的点的个数 ($k-L-1$ 保证 $u$ 不为空)。

因为合并 $right$ 集合的时候,每一个点对仅会出现一次(或者说产生一次贡献),所以区间并不是在 $now$ 的长度 $[min,max]$ 之间,而是任意可行的长度 ($u$ 相同,即 $max$ 以内),因为在这个长度范围内的都是合法,并且下次不会被重复算到(合并后就不会再枚举到这个点对了)。

相当于两个右端点在 $parent$ 树上的 $LCA$ 处计算贡献。

那么就很简单了,建 $SAM$ 用线段树维护 $right$ 集合(用于求区间中点的个数),启发式合并,合并的时候统计 $y$ 合并入 $x$ 时 $y$ 中的点与 $x$ 中的点的贡献。

因为比较懒,所以再用了一个 $set$ 辅助启发式合并。

写完了感觉很奇怪因为并没有用到 $L \leqslant 10$ 这个条件……

代码

不要忘了左右两个区间都行,启发式合并交换 $set$ 的时候不要忘了交换线段树的根(合并了就可以扔掉 $y$ 了)

因为线段树启发式合并是 $O(n log^2 n)$ 的,所以空间也要开到 $O(n log^2 n)$ 。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;

namespace TYC
{
char s[50010];int n,L;
long long ans;

namespace Tree
{
const int M=50000*70+10;

int cnt,ls[M],rs[M],val[M];

void insert(int &root,const int l,const int r,const int pos)
{
if(!root) root=++cnt;
++val[root];
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) insert(ls[root],l,mid,pos);
else insert(rs[root],mid+1,r,pos);
}

int query(const int root,const int l,const int r,const int s,const int e)
{
if(!root) return 0;
if(s<=l&&r<=e) return val[root];
int mid=(l+r)>>1,ans=0;
if(s<=mid) ans+=query(ls[root],l,mid,s,e);
if(e>mid) ans+=query(rs[root],mid+1,r,s,e);
return ans;
}
}

namespace SAM
{
const int N=100010;

int last=1,tot=1,root[N];
struct node
{
int fa,mx,son[26];
}tr[N];

set<int> right[N];
typedef set<int>::iterator iter;

void insert(const int c,const int pos)
{
int now=++tot,p=last;
tr[now].mx=tr[p].mx+1;
right[now].insert(pos);
Tree::insert(root[now],1,n,pos);
while(p&&!tr[p].son[c])
tr[p].son[c]=now,p=tr[p].fa;
if(!p) tr[now].fa=1;
else
{
int q=tr[p].son[c];
if(tr[q].mx==tr[p].mx+1) tr[now].fa=q;
else
{
int clone=++tot;
tr[clone]=tr[q];
tr[clone].mx=tr[p].mx+1;
tr[q].fa=tr[now].fa=clone;
while(p&&tr[p].son[c]==q)
tr[p].son[c]=clone,p=tr[p].fa;
}
}
last=now;
}

void merge(const int x,const int y)
{
if(right[x].size()<right[y].size())
right[x].swap(right[y]),swap(root[x],root[y]);
for(iter it=right[y].begin();it!=right[y].end();it++)
{
int l=max(1,*it-L-tr[x].mx),r=min(n,*it-L-1);
if(l<=r) ans+=Tree::query(root[x],1,n,l,r);
l=*it+L+1,r=min(n,*it+L+tr[x].mx);
if(l<=r) ans+=Tree::query(root[x],1,n,l,r);
}
for(iter it=right[y].begin();it!=right[y].end();it++)
{
Tree::insert(root[x],1,n,*it);
right[x].insert(*it);
}
}

void radix_sort()
{
static int bask[N],q[N];
for(int i=1;i<=tot;i++) bask[tr[i].mx]++;
for(int i=1;i<=tot;i++) bask[i]+=bask[i-1];
for(int i=tot;i;i--) q[bask[tr[i].mx]--]=i;
for(int i=tot;i;i--) merge(tr[q[i]].fa,q[i]);
}
}

void work()
{
scanf("%d%s",&L,s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)
SAM::insert(s[i]-'A',i);
SAM::radix_sort();
printf("%lld\n",ans);
}
}

int main()
{
TYC::work();
return 0;
}