想来SAM也真是太神辣

感觉跳坑里就死在里面出不来了

所以把它拎出来再学（bian）习（shi）一下

后缀自动机可以被理解为所有子串的简明信息。后缀自动机以压缩后的形式包含了一个长度为n的字符串的所有信息，仅需要O(n)的空间。并且，它能在O(n)时间内被构造。（人家都O(n)了没法无视啊！！！）

SAM 是处理字符串相关问题的有力工具, 可以解决包括但不限于以下问题:

• 判断W是否为T的子串
• 判断W是否为T的后缀
• 计算T的不同子串个数
• 计算T的不同子串的总长度
• 计算W在T中的出现次数
• 查找W在T中第一次出现位置
• 查找W在T中所有的出现位置
• 查找T1&T2的最长公共子串
• 查找T1到Tk的最长公共子串
• 查找T的最小循环节
• 查找T的第k小子串
• 查找最短的不是T的子串的字符串
• ......

STATE

$$ \begin{cases} endpos(s_1) \supseteq endpos(s_2), & \text{if } s_1 \sqsupset s_2 \\
endpos(s_1) \cap endpos(s_2) = \emptyset, & \text{otherwise}
\end{cases} $$

SUFFIX LINK

我们给定两个状态$u,v$ 那么 $v = link(u)$即为$u$到$v$的suffix link 且 $maxlen(v) + 1 = minlen(u)$. suffix link 可以把状态之间用suffix link 连起来

STATE'S TRANSITIONS

我们给定一个状态$u$和标记$c$，$trans(u,c) = v$表示状态$u$到状态$v$存在状态转移路径。

我们可以知道以$v$为终点的转移都有一个相同的标记。

令$U_v = \{ u_i \mid trans(u_i, c) = v \}$

我们之前知道对于一个状态$v,substring(v)$中的子串为连续的，又由于状态$v$的转移都有相同的符号，那么$\{ s_i \mid s_i \in substrings(u_i), u_i \in U_v \}$也必为连续的。

SAM的构造步骤

我们对于SAM中的每个状态，维护以下内容

• $maxlen(u)$
• $link(u)$
• $trans(u,\Sigma)$[以$u$为起点的状态转移]

构造过程：

• 新建状态$np$，使$maxlen(np) = maxlen(last) + 1$
• 从状态$last$开始沿着suffix-link path访问每个状态，直到$p = null$或存在$trans(p,T_i)$，令$trans(p,T_i) = np$
• 判断$p$是否为$null$,
  • 若$p = null$，则$link(np) = st, la = np$ 返回第一步
  • 否则$p$为某个存在的状态且$trans(p,T_i) = q$
    • 若$maxlen(p)+1 = maxlen(q)$ 则 $link(np) = q, la = np$ 返回第一步
    • 若$maxlen(p)+1 < maxlen(q)$ 则从$q$状态拆出状态$nq$，令$$link(nq) = link(q) , link(q) = link(np) = nq, la = np$$ 返回第一步

萌萌哒的extend代码QAQ:

void extend(int xx) //mx(p)表示maxlen(p), a[p][xx]表示trans(p,xx), fa[p]表示link(p)
{
	int p = la,np = la = ++tot;
	mx[np] = mx[p]+1;
	while (!a[p][xx] && p) a[p][xx] = np, p = fa[p];
	if (!p) fa[np] = 1;
	else
	{
		int q = a[p][xx];
		if (mx[p]+1 == mx[q]) fa[np] = q;
		else
		{
			int nq = ++tot;
			mx[nq] = mx[p]+1;
			memcpy(a[nq],a[q],sizeof(a[q]));
			fa[nq] = fa[q], fa[np] = fa[q] = nq;
			while (a[p][xx] == q) a[p][xx] = nq, p = fa[p];
		}
	}
}

其他信息的维护

• $minlen(u)$
  • 有$v = link(u) \implies maxlen(v) + 1 = minlen(u)$ 直接在更新$link(u)$时更新$minlen(u)$就可以了
• $first\_endpos(u)$ 表示 $endpos(u)$中最小的下标
  • 对于状态$u$, $endpos(u)$的变更伴随着指向状态$u$的suffix-link的建立。所以我们首先维护$first\_endpos(u)$，在后续的过程中，我们只用沿着suffix-link反向DFS可得$endpos(u)$
  • 对于$first\_endpos(u)$的维护，我们只用
    • 在新建状态$np$时，设$first\_endpos(np)=i$
    • 在新建状态$nq$时，设$$first\_endpos(nq)=first\_endpos(q)$$
• $accept(u)$ 表示接收节点
  • 我们只用看$u$是否在从$la$到$st$的suffix path上即可。因此我们可以在创建SAM后扫一遍suffix path就可以得到所有的接收状态

似乎to be continued...

各种各样的参考资料：

• Suffix Automaton Tutorial （挺详细哒，多看几遍基本能弄懂一点吧qaq，大部分内容来源于此
• cls的冬令营讲稿，感觉真是厉害极辣（%%%
• 后缀自动机与线性构造后缀树 from:fanhq666的博客（%%%
• 后缀自动机：O(N)的构建及应用 某俄文教程的翻译，棒棒哒，有一些用法的介绍

先搬了几道题（无视奇奇怪怪的时间线吧qaq）

BZOJ-3998 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define NN 500050
#define MM 1000010
using namespace std;
int n,t,k;
char ch[NN];
struct SAM
{
	int tot,la,a[MM][30],mx[MM],fa[MM],v[NN],q[MM],val[MM],sum[MM];
	SAM(){ la=++tot;}
	void extend(int xx)
	{
		int p=la,np=la=++tot;
		mx[np]=mx[p]+1,val[np]=1;
		while (!a[p][xx] && p) a[p][xx]=np,p=fa[p];
		if (!p) fa[np]=1;
		else
		{
			int q=a[p][xx];
			if (mx[p]+1==mx[q]) fa[np]=q;
			else
			{
				int nq=++tot; mx[nq]=mx[p]+1;
				memcpy(a[nq],a[q],sizeof(a[q]));
				fa[nq]=fa[q],fa[np]=fa[q]=nq;
				while (a[p][xx]==q) a[p][xx]=nq,p=fa[p];
			}
		}
	}
	void pre()
	{
		for (int i=1;i<=tot;++i) v[mx[i]]++;
		for (int i=1;i<=n;++i) v[i]+=v[i-1];
		for (int i=tot;i;i--) q[v[mx[i]]--]=i;
		for (int i=tot;i;i--)
		{
			int tmp=q[i];
			if (t==1) val[fa[tmp]]+=val[tmp]; else val[tmp]=1;
		}
		val[1]=0;
		for (int i=tot;i;i--)
		{
			int tmp=q[i]; sum[tmp]=val[tmp];
			for (int j=0;j<26;++j) sum[tmp]+=sum[a[tmp][j]];
		}
	}
	void dfs(int xx,int yy)
	{
		if (yy<=val[xx]) return;
		yy-=val[xx];
		for (int i=0;i<26;++i)
			if (int tmp=a[xx][i])
			{
				if(yy<=sum[tmp])
				{
					putchar(i+'a'); dfs(tmp,yy); return;
				}
				yy-=sum[tmp];
			}
	}
}SAM;

int main()
{
	scanf("%s",ch+1); n=strlen(ch+1);
	scanf("%d%d",&t,&k);
	for (int i=1;i<=n;++i) SAM.extend(ch[i]-'a');
	SAM.pre();
	if (k>=SAM.sum[1]) { puts("-1"); return 0;}
	else SAM.dfs(1,k);
	return 0;
}

BZOJ-4516: [Sdoi2016]生成魔咒

听说有SA的做法飞起来

但是由于在学习SAM就用SAM了呀（明明SAM简单辣

其实更新的时候加上$len[i]-len[fa[i]]$就可以了（板子里是$mx[i]-mx[fa[i]]$）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MM = 200010;
int n,x;
LL ans;
struct Sam
{
	int tot,la,mx[MM],fa[MM],val[MM];
	map <int,int> a[MM];
	Sam() { la = ++tot; }
	void extend(int xx)
	{
		int p = la, np = ++tot; la = np;
		mx[np] = mx[p] + 1, val[np] = 1;
		while (!a[p][xx] && p) a[p][xx] = np, p = fa[p];
		if (!p) fa[np] = 1;
		else
		{
			int q = a[p][xx];
			if (mx[p]+1 == mx[q]) fa[np] = q;
			else
			{
				int nq = ++tot;
				mx[nq] = mx[p]+1;
				a[nq] = a[q];
				fa[nq] = fa[q] , fa[np] = fa[q] = nq;
				while (a[p][xx] == q && p) a[p][xx] = nq, p = fa[p];
			}
		}
		ans += mx[np] - mx[fa[np]];
		printf("%lld\n",ans);
	}
}SAM;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&x), SAM.extend(x);
	return 0;
}

BZOJ-4566: [Haoi2016]找相同字符

每个节点对答案的贡献为 $(mx[x]-mx[fa[x]]) \times sz[0][x] \times sz[1][x]$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int NN = 200005,MM = 800005;
int mx[MM],a[MM][26],fa[MM],tot=0,pos,la,q[MM],t[MM],sz[2][MM],n1,n2;
LL ans;
char ch1[NN],ch2[NN];
 
inline void extend(int xx)
{
	int p = la, np = la = ++tot;
	mx[np] = mx[p] + 1;
	while (!a[p][xx] && p) a[p][xx] = np, p = fa[p];
	if (!p) fa[np] = 1;
	else
	{
		int q = a[p][xx];
		if (mx[p]+1 == mx[q]) fa[np] = q;
		else
		{
			int nq = ++tot;
			mx[nq] = mx[p] + 1;
			memcpy(a[nq],a[q],sizeof(a[nq]));
			fa[nq] = fa[q] , fa[np] = fa[q] = nq;
			while (a[p][xx] == q && p) a[p][xx] = nq, p = fa[p];
		}
	}
}
int main()
{
	scanf("%s",ch1); n1 = strlen(ch1);
	scanf("%s",ch2); n2 = strlen(ch2);
	la = ++tot;
	int p=1;
	for (int i=0;i<n1;++i)
	{
		extend(ch1[i]-'a');
		p=a[p][ch1[i]-'a']; sz[0][p]++;
	}
	p = la = 1;
	for (int i=0;i<n2;++i)
	{
		extend(ch2[i]-'a');
		p=a[p][ch2[i]-'a']; sz[1][p]++;
	}
	ans = 0ll;
	for (int i=1;i<=tot;++i) ++t[mx[i]];
	for (int i=1;i<=tot;++i) t[i] += t[i-1];
	for (int i=1;i<=tot;++i) q[t[mx[i]]--] = i;
	for (int i=tot;i;--i) sz[0][fa[q[i]]] += sz[0][q[i]], sz[1][fa[q[i]]] += sz[1][q[i]];
	for (int i=1;i<=tot;++i) ans += (LL)(mx[i] - mx[fa[i]]) * sz[0][i] * sz[1][i];
	printf("%lld\n",ans);
	return 0;
}

HDU5343 MZL'S Circle Zhou

分别对$A$，$B$建立后缀自动机

对$A$进行查找$X$，当$X$的末尾不能接上字符$i$，那么就到$B$中查找所有以i为开头的子串

在两个DAG上DP就可以了【撒花

（答案用unsigned long long存啊啊啊啊，傻逼的我一直死在这里不知道多少次了

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const int NN = 200010;
char ch1[NN],ch2[NN];
LL dp1[NN],dp2[NN];
int T;

struct SAM
{
	int a[NN][26],mx[NN],la,tot,fa[NN];
	void Clr()
	{
		la = tot = 0;
		fa[0] = -1;
		memset(a,-1,sizeof(a));
		mx[0] = 0;
	}
	void extend(int xx)
	{
		int p = la, np = la = ++tot;
		mx[np] = mx[p] + 1;
		while (a[p][xx]==-1 && (~p)) a[p][xx] = np, p = fa[p];
		if (p == -1) fa[np] = 0;
		else
		{
			int q = a[p][xx];
			if (mx[p]+1 == mx[q]) fa[np] = q;
			else
			{
				int nq = ++tot;
				mx[nq] = mx[p] + 1;
				memcpy(a[nq],a[q],sizeof(a[nq]));
				fa[nq] = fa[q] , fa[np] = fa[q] = nq;
				while (a[p][xx] == q && (~p)) a[p][xx] = nq, p = fa[p];
			}
		}
	}
}A,B;

LL DFS2(int xx)
{
	if (xx == -1) return 0;
	LL &pre = dp2[xx];
	if (pre != -1) return pre;
	pre = 1;
	for (int i=0;i<26;++i) pre += DFS2(B.a[xx][i]);
	return pre;
}

LL DFS1(int xx)
{
	LL &pre = dp1[xx];
	if (pre != -1) return pre;
	pre = 1;
	for (int i=0;i<26;++i)
	{
		if (~A.a[xx][i]) pre += DFS1(A.a[xx][i]);
		else pre += DFS2(B.a[0][i]);
	}
	return pre;
}
int main()
{
	scanf("%d",&T);
	for (int _=1;_<=T;++_)
	{
		A.Clr(), B.Clr();
		scanf("%s%s",ch1,ch2);
		int l1 = strlen(ch1), l2 = strlen(ch2);
		for (int i=0;i<l1;++i) A.extend(ch1[i]-'a');
		for (int i=0;i<l2;++i) B.extend(ch2[i]-'a');
		memset(dp1,-1,sizeof(dp1)), memset(dp2,-1,sizeof(dp2));
		printf("%llu\n",DFS1(0));
	}
	return 0;
}

BZOJ-4032：[HEOI2015]最短不公共子串

四个小问，答案都是最小公共子××+1

感觉非常厉害

对于子串，在建立的后缀自动机上跑匹配

对于子序列，采用DP的贪心来做，la[i][j]表示第i位后第一个j出现的位置

然后用BFS四（fu）合（zhi）一就可以了

#include <bits/stdc++.h>
using namespace std;

const int NN = 2001, MM = 4001;
char ch1[NN],ch2[NN];
int l1,l2,la1[NN][26],la2[NN][26],vis[NN][MM],a[MM][26],fa[MM],la=1,tot=1,mx[MM];
struct REC
{ int x,y,l;}tmp,tmpp;
queue <REC> que;

void extend(int xx)
{
	int p = la,np = la = ++tot;
	mx[np] = mx[p]+1;
	while (!a[p][xx] && p) a[p][xx] = np, p = fa[p];
	if (!p) fa[np] = 1;
	else
	{
		int q = a[p][xx];
		if (mx[p]+1 == mx[q]) fa[np] = q;
		else
		{
			int nq = ++tot;
			mx[nq] = mx[p]+1;
			memcpy(a[nq],a[q],sizeof(a[q]));
			fa[nq] = fa[q], fa[np] = fa[q] = nq;
			while (a[p][xx] == q) a[p][xx] = nq, p = fa[p];
		}
	}
}
void Clr()
{
	memset(vis,0,sizeof(vis));
	while (!que.empty()) que.pop();
}
void Solve1()
{
	Clr();
	for (int i=0;i<l1;++i) tmp.x = i, tmp.y = 1, tmp.l = 0, que.push(tmp);
	while (!que.empty())
	{
		tmp = que.front(); que.pop();
		if (tmp.x == l1) continue;
		int nx = tmp.x +1, ny = a[tmp.y][ch1[nx]-'a'];
		if (ny == 0) { printf("%d\n",tmp.l+1); return; }
		if (!vis[nx][ny]) vis[nx][ny] = 1, tmpp.x = nx, tmpp.y = ny, tmpp.l = tmp.l+1, que.push(tmpp);
	}
	printf("%d\n",-1); return;
}
void Solve2()
{
	Clr();
	for (int i=0;i<l1;++i) tmp.x = i, tmp.y = 0, tmp.l = 0, que.push(tmp);
	while (!que.empty())
	{
		tmp = que.front(); que.pop();
		if (tmp.x == l1) continue;
		int nx = tmp.x+1, ny = la2[tmp.y][ch1[nx]-'a'];
		if (ny == 0x3f3f3f3f) { printf("%d\n",tmp.l+1); return;}
		if (!vis[nx][ny]) vis[nx][ny] = 1, tmpp.x = nx, tmpp.y = ny, tmpp.l = tmp.l+1, que.push(tmpp);
	}
	printf("%d\n",-1); return;
}
void Solve3()
{
	Clr(); tmp.x = 0, tmp.y = 1, tmp.l = 0, que.push(tmp);
	while (!que.empty())
	{
		tmp = que.front(); que.pop();
		for (int i=0;i<26;++i)
		{
			int nx = la1[tmp.x][i];
			if (nx == 0x3f3f3f3f) continue;
			int ny = a[tmp.y][ch1[nx]-'a'];
			if (ny == 0) { printf("%d\n",tmp.l+1); return;}
			if (!vis[nx][ny]) vis[nx][ny] = 1, tmpp.x = nx, tmpp.y = ny, tmpp.l = tmp.l+1, que.push(tmpp);
		}
	}
	printf("%d\n",-1); return;
}
void Solve4()
{
	Clr(); tmp.x = 0, tmp.y = 0, tmp.l = 0, que.push(tmp);
	while (!que.empty())
	{
		tmp = que.front(); que.pop();
		for (int i=0;i<26;++i)
		{
			int nx = la1[tmp.x][i], ny = la2[tmp.y][i];
			if (nx == 0x3f3f3f3f) continue;
			if (ny == 0x3f3f3f3f) { printf("%d\n",tmp.l+1); return;}
			if (!vis[nx][ny]) vis[nx][ny] = 1, tmpp.x = nx, tmpp.y = ny, tmpp.l = tmp.l+1, que.push(tmpp);
		}
	}
	printf("%d\n",-1); return;
}
int main()
{
	scanf("%s%s",ch1+1,ch2+1);
	l1 = strlen(ch1+1), l2 = strlen(ch2+1);
	for (int i=1;i<=l2;++i) extend(ch2[i]-'a');
	memset(la1,0x3f,sizeof(la1)), memset(la2,0x3f,sizeof(la2));
	for (int i=0;i<=l1;++i)
		for (int j=i+1;j<=l1;++j)
			la1[i][ch1[j]-'a'] = min(j,la1[i][ch1[j]-'a']);
	for (int i=0;i<=l2;++i)
		for (int j=i+1;j<=l2;++j)
			la2[i][ch2[j]-'a'] = min(j,la2[i][ch2[j]-'a']);
	Solve1(), Solve2(), Solve3(), Solve4();
	return 0;
}

BZOJ-3238: [Ahoi2013]差异

我们需要一个后缀树，然后两个后缀的lcp就是它们lca的len，我们在后缀树上进行DP就可以了。

后缀树呢我们可以通过反序后缀自动机得到。

#include <bits/stdc++.h>
using namespace std;
const int NN = 1000010;
typedef long long LL;
int val[NN],fa[NN],a[NN][27],mx[NN],tot=1,cnt,head[NN],la=1,len;
LL ans;
struct E
{
	int ne,v;
}e[NN];
inline void extend(int xx)
{
	int p = la, np = la = ++tot;
	mx[np] = mx[p] + 1, val[np] = 1;
	while (!a[p][xx] && p) a[p][xx] = np, p = fa[p];
	if (!p) fa[np] = 1;
	else
	{
		int q = a[p][xx];
		if (mx[p]+1 == mx[q]) fa[np] = q;
		else
		{
			int nq = ++tot;
			mx[nq] = mx[p] + 1;
			memcpy(a[nq],a[q],sizeof(a[nq]));
			fa[nq] = fa[q] , fa[np] = fa[q] = nq;
			while (a[p][xx] == q && p) a[p][xx] = nq, p = fa[p];
		}
	}
}
void Build(int xx,int yy)
{
	e[++cnt].ne = head[xx], head[xx] = cnt, e[cnt].v = yy;
}

void DP(int xx,int p)
{
	for (int i=head[xx];i;i=e[i].ne)
	{
		DP(e[i].v,xx);
		val[xx] += val[e[i].v];
	}
	mx[xx] -= mx[p];
	ans -= (LL)val[xx] * (val[xx]-1) * mx[xx];
}
char ch[NN];
int main()
{
	scanf("%s",ch);
	len = strlen(ch);
	for (int i=len-1;i>=0;--i) extend(ch[i]-'a');
	ans = (LL) (len-1) * len * (len+1) >> 1ll;
	for (int i=2;i<=tot;++i) Build(fa[i],i);
	for (int i=head[1];i;i=e[i].ne) DP(e[i].v,1);
	printf("%lld\n",ans);
	return 0;
}

BZOJ-3926

神奇的题目描述啊。。。感觉语文不好的后果来了

ZJOI的题目呢。。。马上省选了好虚。。强省蒟蒻滚粗无疑辣。。

#include <iostream> 
#include <cstdio> 
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#define LL long long
#define MM 4000005
#define NN 100005
using namespace std;
LL ans;
int n,c,cc[NN],d[NN],tot=0,head[NN];
struct Edge
{
	int ne,v;
}e[NN<<1];
void Build(int xx,int yy)
{
	e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy;
	e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx;
}
struct SAM
{
	int cnt,fa[MM],a[MM][10],mx[MM];
	SAM(){cnt=1;}
	int extend(int p,int c)
	{
		int np=++cnt; mx[np]=mx[p]+1;
		while (!a[p][c] && p) a[p][c]=np, p=fa[p];
		if (!p) fa[np]=1;
		else
		{
			int q=a[p][c];
			if (mx[p]+1==mx[q]) fa[np]=q;
			else
			{
				int nq=++cnt;mx[nq]=mx[p]+1;
				memcpy(a[nq],a[q],sizeof(a[q]));
				fa[nq]=fa[q], fa[np]=fa[q]=nq;
				while (a[p][c]==q) a[p][c]=nq, p=fa[p];
			}
		}
		return np;
	}
	void solve()
	{
		for (int i=1;i<=cnt;++i) ans+=mx[i]-mx[fa[i]];
	}
}Sam;
void DFS(int x,int fa,int p)
{
	int t=Sam.extend(p,cc[x]);
	for (int i=head[x];i;i=e[i].ne)
		if (e[i].v!=fa)
			DFS(e[i].v,x,t);
}
int main()
{
	scanf("%d%d",&n,&c);
	for (int i=1;i<=n;++i) scanf("%d",&cc[i]);
	int x,y;
	for (int i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		Build(x,y);
		d[x]++, d[y]++;
	}
	for (int i=1;i<=n;++i)
		if (d[i]==1) DFS(i,0,1);
	Sam.solve();
	printf("%lld\n",ans);
	return 0;
}

BZOJ-4199

唔。。2015年的NOI题目呢。。。别忘了考虑负数。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define NN 600006
#define INF 2e18
using namespace std;
LL mav[NN],ma1[NN],ma2[NN],mi1[NN],mi2[NN],head[NN],n,m,a[NN],size[NN],ans[NN],tot=0;
bool vis[NN];
char ch[NN];
struct Edge
{
	int v,ne,w;
}e[NN];
void Build(LL xx,LL yy,LL zz)
{
	e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz;
}
struct SAM
{
	LL cnt,la,ne[NN][26],fa[NN],mx[NN],t[NN],now,tmp,nx[NN];
	SAM(){la=++cnt;}
	void extend(int xx)
	{
		LL p=la,np=la=++cnt,c=ch[xx]-'a'; 
		mx[np]=mx[p]+1, t[np]=xx;
		while (!ne[p][c] && p) ne[p][c]=np, p=fa[p];
		if (!p) fa[np]=1;
		else
		{
			LL q=ne[p][c];
			if (mx[p]+1==mx[q]) fa[np]=q;
			else
			{
				LL nq=++cnt; mx[nq]=mx[p]+1;
				memcpy(ne[nq],ne[q],sizeof(ne[q]));
				fa[nq]=fa[q], fa[np]=fa[q]=nq;
				while (ne[p][c]==q) ne[p][c]=nq, p=fa[p];
			}
		}
	}
	void DFS(LL xx,LL h)
	{
		if (t[xx]) ma1[xx]=mi1[xx]=a[t[xx]], size[xx]=1;
			else ma1[xx]=-INF,mi1[xx]=INF, size[xx]=0;
		ma2[xx]=-INF, mi2[xx]=INF;
		for (LL i=head[xx];i;i=e[i].ne)
		{
			LL yy=e[i].v;
			DFS(yy,h+e[i].w);
			if (ma1[yy]>ma1[xx])
			{
				ma2[xx]=ma1[xx], ma1[xx]=ma1[yy];
				if (ma2[yy]>ma2[xx]) ma2[xx]=ma2[yy];
			}
			else
			if (ma1[yy]>ma2[xx]) ma2[xx]=ma1[yy];
			if (mi1[yy]<mi1[xx])
			{
				mi2[xx]=mi1[xx], mi1[xx]=mi1[yy];
				if (mi2[yy]<mi2[xx]) mi2[xx]=mi2[yy];
			}
			else
			if (mi1[yy]<mi2[xx]) mi2[xx]=mi1[yy];
			size[xx]+=size[yy], nx[xx]+=nx[yy];
		}
		now=-INF; tmp=(size[xx]*(size[xx]-1))/2;
		if (size[xx]>=4)now=max(max(ma1[xx]*ma2[xx],mi1[xx]*mi2[xx]),max(ma1[xx]*mi2[xx],ma2[xx]*mi1[xx]));
		else
		if (size[xx]>=3) now=max(max(ma1[xx]*ma2[xx],mi1[xx]*mi2[xx]),ma1[xx]*mi1[xx]);
		else
		if (size[xx]>=2) now=ma1[xx]*ma2[xx];
		if (now!=INF) ans[h]+=tmp-nx[xx], mav[h]=max(mav[h],now);
		nx[xx]+=tmp-nx[xx];
	}
}Sam;
int main()
{
	scanf("%lld",&n);
	scanf("%s",ch+1);
	for (LL i=n;i;i--) Sam.extend(i);
	vis[1]=1;
	for (LL i=1;i<=Sam.cnt;++i)
		if (Sam.t[i]&&!vis[i])
			for (LL j=i;!vis[j];vis[j]=1,j=Sam.fa[j]) Build(Sam.fa[j],j,Sam.mx[j]-Sam.mx[Sam.fa[j]]);
	for (LL i=0;i<=n;++i) mav[i]=-INF;
	for (LL i=1;i<=n;++i) scanf("%lld",&a[i]);
	Sam.DFS(1,0);
	for (LL i=n-1;i>=0;--i) ans[i]=ans[i]+ans[i+1], mav[i]=max(mav[i],mav[i+1]);
	for (LL i=0;i<n;++i)
	{
		if (mav[i]==-INF) mav[i]=0;
		printf("%lld %lld\n",ans[i],mav[i]);
	}
	return 0;
}