[[HDU-6791] 2020HDU多校第三场T1](http://acm.hdu.edu.cn/showproblem.php?pid=6791)(回文自动机)

Posted on Edited on In

#[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");
		}
	}
}