Description：

给定一个字符串和其每个位置相应的权值，求满足权值和等于其在所有子串中的排名(从大到小)的子串个数。

$1\leqslant n\leqslant 200000$

Solution：

首先非常容易发现对于从某个位置开始的所有子串，他们的权值单调不降，排名单调递减，因此排名 $-$ 权值是严格单调的，那么也就是说我们可以对每个位置开始的所有子串二分一下找到那个权值 $=$ 排名的位置。

但是还有一个问题，就是如何快速计算子串 $(l,r)$ 的排名。

首先如果他没有在这个和他前一个的 $lcp$ 部分，那他的排名为 $sh[n]-sh[rnk[l]-1]-(r-l-hei[rnk[l]])$ ，如果他在它和前一个的 $lcp$ 部分，我们可以用 $ST$ 表 $+$ 二分找到第一个这个子串，然后用上面那个公式查询即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 400010

char s[MAXN];

int sa[MAXN],rnk[MAXN],height[MAXN];

int c1[MAXN],c2[MAXN];

int c[MAXN];

void make_SA(int n,int m)

{

    int *x = c1,*y = c2;

    for(int i = 1;i <= m;++i)c[i] = 0;

    for(int i = 1;i <= n;++i)++c[x[i] = s[i]];

    for(int i = 1;i <= m;++i)c[i] += c[i - 1];

    for(int i = n;i >= 1;--i)sa[c[x[i]]--] = i;

    int p = 0;

    for(int k = 1;k <= n;k = k << 1)

    {

        p = 0;

        for(int i = n - k + 1;i <= n;++i)y[++p] = i;

        for(int i = 1;i <= n;++i)if(sa[i] > k)y[++p] = sa[i] - k;

        for(int i = 1;i <= m;++i)c[i] = 0;

        for(int i = 1;i <= n;++i)++c[x[y[i]]];

        for(int i = 1;i <= m;++i)c[i] += c[i - 1];

        for(int i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

        p = 1;

        swap(x,y);

        x[sa[1]] = 1;

        for(int i = 2;i <= n;++i)

        {

            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

        }

        if(p >= n)break;

        m = p;

    }

    for(int i = 1;i <= n;++i)rnk[sa[i]] = i;

    int k = 0;

    for(int i = 1;i <= n;++i)

    {

        if(rnk[i] == 1)continue;

        if(k)--k;

        int j = sa[rnk[i] - 1];

        while(j + k <= n && i + k <= n && s[i + k] == s[j + k])++k;

        height[rnk[i]] = k;

    }

    return;

}

int f[MAXN][19];

int lg[MAXN];

int lcp(int a,int b)

{

    if(a == b)return n - a + 1;

    a = rnk[a];b = rnk[b];if(a > b)swap(a,b);++a;

    int len = lg[b - a + 1];

    return min(f[a][len],f[b - (1 << len) + 1][len]);

}

int val[MAXN];

long long sumh[MAXN];

long long calc(int L,int R)

{

	int le = R - L + 1;

	if(le > height[rnk[L]])return sumh[n] - sumh[rnk[L] - 1] - (R - L - height[rnk[L]]);

	else

	{

		int l = 1,r = rnk[L],mid;

		while(l < r)

		{

			mid = ((l + r) >> 1);

			if(lcp(sa[mid],L) >= R - L + 1)r = mid;

			else l = mid + 1;

		}

		L = sa[l];R = L + le - 1;

		return sumh[n] - sumh[rnk[L] - 1] - (R - L - height[rnk[L]]);

	}

}

long long sum[MAXN];

int cnt = 0;

int ans[MAXN][2];

int main()

{

	scanf("%s",s + 1);

	n = strlen(s + 1);

	make_SA(n,256);

	for(int i = 1;i <= n;++i)f[i][0] = height[i];

	for(int k = 1;k <= 18;++k)

		for(int i = 1;i <= n - (1 << k) + 1;++i)

			f[i][k] = min(f[i][k - 1],f[i + (1 << (k - 1))][k - 1]);

	for(int i = 2;i <= n;++i)lg[i] = lg[i >> 1] + 1;

	for(int i = 1;i <= n;++i)sumh[i] = sumh[i - 1] + n - sa[i] + 1 - height[i];

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + val[i];

	for(int i = 1;i <= n;++i)

	{

		int l = i,r = n,mid;

		while(l < r)

		{

			mid = ((l + r + 1) >> 1);

			if(calc(i,mid) >= sum[mid] - sum[i - 1])l = mid;

			else r = mid - 1;

		}

		if(calc(i,l) == sum[l] - sum[i - 1])

		{

			++cnt;

			ans[cnt][0] = i;ans[cnt][1] = l;

		}

	}

	cout << cnt << endl;

	for(int i = 1;i <= cnt;++i)

	{

		printf("%d %d\n",ans[i][0],ans[i][1]);

	}

    return 0;

}