[HDU-6791] 2020HDU多校第三场T1(回文自动机)

前置知识：

1.字符串的$\text{Border}$

2.回文自动机

3.回文串与$\text{Border}$

3.1:回文串的$\text{Border}$也是回文串

若有回文串$S$的一个$\text{Border} :T$，则$S_{1,|T|}=S_{|S|-|T|+1,|S|}=reverse(S_{1,|T|})$

故$T$也是一个回文串

3.2:遍历回文自动机的$fail$链，能得到当前串的所有$\text{Border}$(基于3.1得到)

约定:串$S$的$\text{Border}$集合为$B(S)$，字符集为$\Sigma$

题意:

设随机空串末尾添加$\Sigma$中的字符，第一次出现子串$S$的期望长度为$E(S)$

给定一个串，每次查询它的两个回文子串$A,B$，比较$E(A),E(B)$

起源？

一切的起源都是” 国家集训队论文2018 :1-浅谈生成函数在掷骰子问题上的应用 “的一个结论。。。

还有为什么会是回文子串呢？因为只有回文自动机能访问子串的所有$\text{Border}$。。。

结论 以及 口胡证明?

$\begin{aligned}E(S)=\sum_{T\in B(S)}|\Sigma|^{|T|}\end{aligned}$~~(???)~~ 在原论文给出了生成函数性的证明，实际可以直接口胡(好吧也差不多)，大致分成两个步骤 1.$E(S)=\sum_{i=0}^{\infty}$长度为$i$依然不包含$S$的概率(即把长度为$i$时恰好合法转化为了$0..i-1$时不合法) 2.设所有长度下不合法的串集合为$G$(每个不合法串有概率$G(T)$)，合法的串集合为$F$(每个合法串也有概率$F(T)$) 由第一步$E(S)=\sum G(T)$，合法串的概率不会重复，所以$\sum F(T)=1$ 考虑$G$中所有的串，如果在后面接上$S$必然合法，但是可能在更早的时候就结束了，这是必然满足接上的前缀是$\text{Border}$ 也就是说，在$G$集合后面接上$S$后，不仅会得到$F$集合，还会得到$F$集合后面额外接上$|S|-|R|,(R\in B(S))$长度字符的状态 所以有$\sum G(T)\cdot (\frac{1} {|\Sigma|})^{|S|}=\sum_{R\in B(S)}\sum F(T)\cdot (\frac{1} {|\Sigma|})^{|S|-|R|}$ 化简且带入$\sum F(T)=1$，得到$E(S)=\sum G(T)=\begin{aligned}\sum_{R\in B(S)}|\Sigma|^{|R|}\end{aligned}$

那么比较问题就落到了比较$\text{Border}$上面

视答案为为一个$26$进制数从高位到低位比较，转化为直接从大到小比较$\text{Border}$序列的字典序即可

建出回文自动机后，倍增找到当前查询串对应的状态，所有的$\text{Border}$就是$fail$链上所有非空状态长度

比较字典序可以

1.倍增+hash

2.可以根据$\text{Border}$的性质分解为等差数列后暴力比较

3.像后缀数组一样，倍增地去为所有节点的字典序排序，这样查询是$O(1)$的

hash应该细节比较少，但是常数大

以下是hash版本

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0;int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e5+10;
const ll P1=1e9+13,P2=19260817;
const ll K1=123213,K2=342525;

int n;
char s[N];
int now,len[N],fail[N],nxt[N][26],pos[N],cnt;
int Pow1[N],Pow2[N];
int fa[N][18],h1[N][18],h2[N][18];

void Init(){
	rep(i,0,cnt) memset(nxt[i],fail[i]=0,104);
	len[1]=-1;
	fail[now=0]=fail[1]=cnt=1;
}
int Find(int x,int y){
	while(s[y]!=s[y-len[x]-1]) x=fail[x];
	return x;
}
void Extend(int i,int c){
	now=Find(now,i);
	if(!nxt[now][c]){
		fail[++cnt]=nxt[Find(fail[now],i)][c];
		len[nxt[now][c]=cnt]=len[now]+2;
	}
	pos[i]=now=nxt[now][c];
}
int Que(int l,int p){
	l=p-l+1,p=pos[p];
	drep(i,17,0) if(len[fa[p][i]]>=l) p=fa[p][i];
	return p;
}

int main(){
	rep(i,Pow1[0]=Pow2[0]=1,N-1) Pow1[i]=1ll*Pow1[i-1]*K1%P1,Pow2[i]=Pow2[i-1]*K2%P2;
	rep(kase,1,rd()){
		Init(),n=rd(),scanf("%s",s+1);
		rep(i,1,n) Extend(i,s[i]-'a');
		rep(i,2,cnt) {
			fa[i][0]=fail[i],h1[i][0]=h2[i][0]=len[i];
			rep(j,1,17){
				fa[i][j]=fa[fa[i][j-1]][j-1];
				if(fa[i][j]>1){
					h1[i][j]=(1ll*h1[i][j-1]*Pow1[1<<(j-1)]+h1[fa[i][j-1]][j-1])%P1;
					h2[i][j]=(1ll*h2[i][j-1]*Pow2[1<<(j-1)]+h2[fa[i][j-1]][j-1])%P2;
				}
			}
		}
		rep(q,1,rd()) {
			int A=rd(),B=rd(),C=rd(),D=rd();
			A=Que(A,B),C=Que(C,D);
			drep(i,17,0) if(fa[A][i]>1 && fa[C][i]>1 && h1[A][i]==h1[C][i] && h2[A][i]==h2[C][i]) A=fa[A][i],C=fa[C][i];
			A=max(len[A],0),C=max(len[C],0);
			if(A==C) puts("draw");
			else if(A<C) puts("sjfnb");
			else puts("cslnb");
		}
	}
}