LOJ 6031（雅礼集训2017 Day1）字符串（后缀自动机+倍增）

发表于 |
字数统计: 1,595字 | 阅读时长 ≈ 8min

「雅礼集训 2017 Day1」字符串

问题描述

令 $ s $ 与 $ w $ 为两字符串，定义：

  1. $ w[l, r] $ 表示字符串 $ w $ 在区间 $ [l, r] $ 中的子串；
  2. $ w $ 在 $ s $ 中出现的频率定义为$ w $ 在 $ s $ 中出现的次数；
  3. $ f(s, w, l, r) $ 表示 $ w[l, r] $ 在 $ s $ 中出现的频率。

比如 $ f(\texttt{ababa}, \texttt{aba}, 1, 3) = 2 $。

现在给定串 $ s $，$ m $ 个区间 $ [l, r] $ 和长度 $ k $，你要回答 $ q $ 个询问，每个询问给你一个长度为 $ k $ 的字符串 $ w $ 和两个整数 $ a, b $，求：

$$ \sum\limits_{i = a} ^ b f(s, w, l_i, r_i) $$

输入格式

第一行四个整数 $ n, m, q, k $，$ n $ 表示 $ s $ 的长度。

接下来一行一个长为 $ s $ 的字符串 $ s $。

接下来 $ m $ 行，每行两个整数表示 $ l_i, r_i $。

接下来 $ q $ 行，每行一个字符串 $ w $，两个整数 $ a, b $。

输出格式

对于每个询问一行，输出答案。

样例输入

8 5 3 3

abacdaba

0 2

1 2

0 0

2 2

1 2

dab 1 4

bac 2 3

eeb 1 3

样例输出

7

3

2

提示

对于 $ 10\% $ 的数据，$ n, m, k, q \leq 10 $；

对于 $ 30\% $ 的数据，满足 $ n, m, k, q \leq 10 ^ 2 $；

对于 $ 50\% $ 的数据，满足 $ n, m, k, q \leq 10 ^ 4 $；

对于 $ 100\% $ 的数据，满足 $ n, m, k, q \leq 10 ^ 5, \sum w \leq 10 ^ 5 $，字符串由小写英文字母构成。

注意到这题给出的条件$\sum w\leq 10^5$，即$qk\leq10^5$，那么这个条件就是解题的关键了。

由于$q,k$不会同时很大，因此我们考虑设计两种算法，分别针对$q$很大和$k$很大的情况。

对于$q$很大的情况，此时$k$比较小，那么由于不同的区间最多有$k^2$个，那么$m$个区间中会存在一些重复，考虑将这些重复的部分一起计算，令$Q[i][j]$表示左端点在$i$，右端点在$j$的区间集合。

对于每个询问，我们可以用$k^2$的时间计算出每个区间在$s$中出现的次数，具体做法是建出$s$的后缀自动机，枚举左端点，右端点在自动机上跑，然后所在位置的$right$集合大小就是出现次数。

然后我们枚举这$k^2$个区间，看看有多少个是在$[a,b]$之间的。这个可以二分查找。也可以离线用莫队来处理，如果用莫队就只需要将计算出来的出现次数存在$cnt[i][j]$里面，答案就是$cnt[i][j]\times (i,j)在[a,b]中出现次数$。

如果用二分查找，复杂度是$O(qk^2\log m)$，如果用莫队，复杂度是$O(qk^2+m\sqrt{m})$

对于$k$很大的情况，由于q比较小，我们可以直接$O(qm)$对每个询问暴力查找每个区间的出现次数，如果能在较低复杂度内查找$w[l,r]$在$s$中出现次数，那么可以解决这个问题。然后这个可以考虑在$SAM$上倍增，考虑到子串就是前缀的后缀，那么我们先将$w$在自动机上匹配一次，记录下每个前缀在自动机上的匹配位置，然后就可以在$parent$树上倍增查找到子串位置了。

时间复杂度$O(qm\log n+qk)$

既然这样，我们可以设置一个阈值$S=\sqrt{10^5}$，然后当$k<S$时用算法一，否则用算法二。

代码：

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
119
120
121
122
123
124
125
126
127
128
129
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 400005
#define ll long long
using namespace std;
const int K=400;
ll Ans;
int n,m,q,k,L[N],R[N];
char s[N],w[N];
namespace SAM
{
	int tot,rt,las,par[N][20],Max[N],son[N][26],si[N];
	bool vis[N];
	vector<int>G[N];
	int NP(int v){return Max[++tot]=v,tot;}
	void Init(){tot=0;las=rt=++tot;}
	void Ins(int t)
	{
		int p=las,q,np,nq;
		np=NP(Max[p]+1);si[np]=1;
		while(p&&!son[p][t])son[p][t]=np,p=par[p][0];
		if(!p)par[np][0]=rt;
		else
		{
			q=son[p][t];
			if(Max[q]==Max[p]+1)par[np][0]=q;
			else
			{
				nq=NP(Max[p]+1);
				memcpy(son[nq],son[q],sizeof(son[q]));
				par[nq][0]=par[q][0];
				par[q][0]=par[np][0]=nq;
				while(p&&son[p][t]==q)son[p][t]=nq,p=par[p][0];
			}
		}
		las=np;
	}
	void Build(){for(int i=2;i<=tot;i++)G[par[i][0]].push_back(i);}
	void DFS(int x)
	{
		int i,y;
		for(i=1;i<=18;i++)par[x][i]=par[par[x][i-1]][i-1];
		for(i=0;i<G[x].size();i++)
		{
			y=G[x][i];DFS(y);
			si[x]+=si[y];
		}
	}
	void Match(int &p,int t,int &len)
	{
		while(p&&!son[p][t])p=par[p][0],len=Max[p];
		if(p)p=son[p][t],len++;
		else p=rt,len=0;
	}
	int Jump(int p,int l)
	{
		for(int i=18;i>=0;i--)if(Max[par[p][i]]>=l)p=par[p][i];
		return p;
	}
}
void Solve1()
{
	vector<int>Q[K][K];
	int i,j,a,b,p,l,r,cnt=0;
	for(i=0;i<m;i++)Q[L[i]][R[i]].push_back(i);
	while(q--)
	{
		scanf("%s%d%d",w,&a,&b);Ans=0;
		for(i=0;i<k;i++)
		{
			p=SAM::rt;
			for(j=i;j<k;j++)
			{
				p=SAM::son[p][w[j]-'a'];
				if(p==0)break;
				cnt=SAM::si[p];
				l=lower_bound(Q[i][j].begin(),Q[i][j].end(),a)-Q[i][j].begin();
				r=upper_bound(Q[i][j].begin(),Q[i][j].end(),b)-Q[i][j].begin();
				Ans+=1ll*cnt*(r-l);
			}
		}
		printf("%lld\n",Ans);
	}
}
void Solve2()
{
	int i,l,r,a,b,p,len[N]={0},pos[N]={0},tmp;
	while(q--)
	{
		scanf("%s%d%d",w,&a,&b);Ans=0;
		p=SAM::rt;tmp=0;
		for(i=0;i<k;i++)
		{
			SAM::Match(p,w[i]-'a',tmp);
			pos[i]=p;len[i]=tmp;
		}
		for(i=a;i<=b;i++)
		{
			if(R[i]-L[i]+1>len[R[i]])continue;
			p=SAM::Jump(pos[R[i]],R[i]-L[i]+1);
			Ans+=SAM::si[p];
		}
		printf("%lld\n",Ans);
	}
}
int main_main()
{
	int i;
	scanf("%d%d%d%d%s",&n,&m,&q,&k,s);
	for(i=0;i<m;i++)scanf("%d%d",&L[i],&R[i]);
	SAM::Init();
	for(i=0;i<n;i++)SAM::Ins(s[i]-'a');
	SAM::Build();
	SAM::DFS(SAM::rt);
	if(k<K)Solve1();
	else Solve2();
}
const int main_stack=16;    
char my_stack[128<<20];    
int main() {    
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");    
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");    
  main_main();    
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");    
  return 0;    
}