要求的东西很奇怪,但容易发现有个单调性。

如果定住区间 \(L\) ,当 \(R\) 变大时,\(rk\) 变小, \(sum\) 变大,可能的相等的点最多一个,直接可以二分出来。

所以我们只要 \(SAM\) 实现求子串排名就好了……

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
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define X first
#define Y second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=400005;
char s[maxn];
int lst,N_sam,ch[maxn][26],par[maxn],Max[maxn],pos[maxn],ipos[maxn];
int newnode(int t){
N_sam++; Max[N_sam]=t; return N_sam;
}
void Extend(int c,int id){
int np=newnode(Max[lst]+1); pos[np]=id; ipos[id]=np;
int p=lst; while(p&&!ch[p][c]) ch[p][c]=np, p=par[p];
if(!p) par[np]=1; else{
int q=ch[p][c];
if(Max[q]==Max[p]+1) par[np]=q; else{
int nq=newnode(Max[p]+1); pos[nq]=pos[q];
memcpy(ch[nq],ch[q],sizeof(ch[q]));
par[nq]=par[q]; par[q]=nq; par[np]=nq;
while(p&&ch[p][c]==q) ch[p][c]=nq, p=par[p];
}
}
lst=np;
}
int n,son[maxn][26],ans,anc[maxn][20];
int dfn[maxn],idfn[maxn],Tim;
LL sum[maxn],rk[maxn];
void dfs(int x){
dfn[x]=++Tim; idfn[Tim]=x;
for(int i=1;i<=19;i++) anc[x][i]=anc[anc[x][i-1]][i-1];
for(int i=0;i<=25;i++)
if(son[x][i]) anc[son[x][i]][0]=x, dfs(son[x][i]);
}
LL getRank(int p,int len){
for(int i=19;i>=0;i--)
if(Max[anc[p][i]]>=len) p=anc[p][i];
return rk[p]+Max[p]-len;
}
vector< pair<int,int> > V;
int main(){
scanf("%s",s+1); n=strlen(s+1);
lst=newnode(0);
for(int i=n;i>=1;i--) Extend(s[i]-'a',i);
for(int i=2;i<=N_sam;i++)
son[par[i]][s[pos[i]+Max[par[i]]]-'a']=i;
anc[1][0]=1; dfs(1);
for(int i=1;i<=n;i++) scanf("%d",&sum[i]), sum[i]+=sum[i-1];
rk[idfn[N_sam]]=1;
for(int i=N_sam-1;i>=1;i--){
int x=idfn[i],y=idfn[i+1];
rk[x]=rk[y]+Max[y]-Max[par[y]];
}
for(int i=1;i<=n;i++){
int L=1,R=n-i+1,res=0;
while(L<=R){
int mid=(L+R)>>1; LL t=sum[i+mid-1]-sum[i-1]-getRank(ipos[i],mid);
if(t==0){ res=mid; break; }
if(t<0) L=mid+1; else R=mid-1;
}
if(res) V.push_back(mp(i,i+res-1));
}
sort(V.begin(),V.end());
printf("%d\n",V.size());
for(int i=0;i<V.size();i++) printf("%d %d\n",V[i].X,V[i].Y);
return 0;
}