题面

1024MB，4s

题解

我们把文本串建后缀自动机，然后把询问离线下来，按右端点放在模式串上，然后可以找到模式串每个前缀在SAM上的对应节点，获得子串的出现次数，更新答案。这个是 $O(n^2)$ 的。

我们可以用莫队算法，先预处理出后缀树上每个点 $p$ 的祖先中最大的 $t\times len$ ，然后由于莫队算法中扩展到的区间都是确定的，我们可以把莫队中出现的区间再次“离线”到后缀树上，算出每个区间对应的SAM上的点 $p$ ，贡献就是 $p$ 的出现次数乘当前 $p$ 的有效长度，以及 $p$ 祖先中的最大 $t\times len$ 。时间复杂度 $O(n\sqrt{n})$ 。

但是这样跑的有点慢，我们其实可以直接暴力剪枝。

回到那个 $O(n^2)$ 的做法，我们是得到了当前前缀对应点 $p$ 后，在 $len[p]\sim len[fa[p]]-1$ 之间枚举算贡献，但是过程中如果答案小于了 $p$ 祖先中最大的 $t\times len$ ，就可以直接跳出了。另外，也不用每次跳一步父亲，可以每次直接跳到 $t[q]\times len[q]$ 最大的 $p$ 的祖先 $q$ 。可以证明跳祖先次数上限是 $O(\sqrt{n})$ 的，暴力枚举的次数也很小，跟字符集大小有关。每次枚举的贡献用分块维护，$O(1)$ 修改，$O(\sqrt{n})$ 查询。这道题时限四秒，这个做法四舍五入只跑了五百毫秒。

CODE

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#pragma GCC optimize(2)
using namespace std;
#define MAXN 100005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
#define SQ 317
int xchar() {
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {putnum(x);putchar(c);}

int n,m,s,o,k;
inline LL Max(LL a,LL b) {return a>b ? a:b;}
char s1[MAXN],s2[MAXN];
struct SAM{
	int s[26],len,fa;
	SAM(){memset(s,0,sizeof(s));len=fa=0;}
}sam[MAXN<<1];
int las = 1,cnt = 1;
int addsam(int c) {
	int p = las,np = (las = ++ cnt);
	sam[np].len = sam[p].len + 1;
	for(;p&&!sam[p].s[c];p=sam[p].fa)sam[p].s[c] = np;
	if(!p) sam[np].fa = 1;
	else {
		int q = sam[p].s[c];
		if(sam[q].len == sam[p].len + 1) sam[np].fa = q;
		else {
			int nq = ++ cnt; sam[nq] = sam[q];
			sam[nq].len = sam[p].len + 1;
			sam[np].fa = sam[q].fa = nq;
			for(;p&&sam[p].s[c]==q;p=sam[p].fa)sam[p].s[c]=nq;
		}
	}return np;
}
vector<int> g[MAXN<<1];
int ct[MAXN<<1],tp[MAXN<<1];
LL wt[MAXN<<1];
void dfs(int x) {for(int y:g[x])dfs(y),ct[x]+=ct[y];}
void dfs2(int x) {
	wt[x] = sam[x].len *1ll* ct[x];
	tp[x] = sam[x].fa;
	if(wt[tp[sam[x].fa]] >= wt[tp[x]]) tp[x] = tp[sam[x].fa];
	for(int y:g[x]) dfs2(y);
}
int bl[MAXN];
LL mw[MAXN],mb[MAXN];
inline void addp(int x,LL y) {
	mw[x] = Max(mw[x],y);
	mb[bl[x]] = Max(mb[bl[x]],y);
}
int ql[MAXN];
vector<int> bu[MAXN];
LL as[MAXN];
int main() {
	scanf("%s",s1 + 1);
	n = strlen(s1 + 1);
	for(int i = 1;i <= n;i ++) {
		bl[i] = i/SQ+1;
	}
	scanf("%s",s2 + 1);
	m = strlen(s2 + 1);
	for(int i = 1;i <= m;i ++) {
		s = addsam(s2[i]-'a');
		ct[s] ++;
	}
	for(int i = 2;i <= cnt;i ++) g[sam[i].fa].push_back(i);
	dfs(1); dfs2(1);
	int Q = read(),flag = 1;
	for(int i = 1;i <= Q;i ++) {
		ql[i] = read();o = read();
		bu[o].push_back(i);
		if(ql[i] > 1) flag = 0;
	}
	if(flag) {
		LL ans = 0;
		int p = 1,le = 0;
		for(int i = 1;i <= n;i ++) {
			int c = s1[i]-'a';
			while(p > 1 && !sam[p].s[c]) p = sam[p].fa,le = sam[p].len;
			if(sam[p].s[c]) p = sam[p].s[c],le ++;
			ans = max(ans,le*1ll*ct[p]);
			ans = max(ans,wt[tp[p]]);
			for(int x:bu[i]) {
				as[x] = ans;
			}
		}
		for(int i = 1;i <= Q;i ++) {
			AIput(as[i],'\n');
		} return 0;
	}
	int p = 1,le = 0;
	for(int i = 1;i <= n;i ++) {
		int c = s1[i]-'a';
		while(p > 1 && !sam[p].s[c]) p = sam[p].fa,le = sam[p].len;
		if(sam[p].s[c]) p = sam[p].s[c],le ++;
		int pp = p,ll = le;
		while(pp) {
			int nx = tp[pp];
			for(;ll > sam[sam[pp].fa].len && ll*1ll*ct[pp] > wt[nx];ll --) {
				addp(i-ll+1,ll*1ll*ct[pp]);
			} pp = nx; ll = sam[pp].len;
		}
		for(int x:bu[i]) {
			s = ql[x];
			for(int j = s;bl[j] == bl[s];j ++) as[x] = Max(as[x],mw[j]);
			for(int j = bl[s]+1;j <= bl[n];j ++) as[x] = Max(as[x],mb[j]);
		}
	}
	for(int i = 1;i <= Q;i ++) {
		AIput(as[i],'\n');
	}
	return 0;
}
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153