G题: Magic Spells

原题链接:https://ac.nowcoder.com/acm/contest/33194/G

题目大意

求字符串集合中本质不同的公共回文子串的数量。
字符串数量 $k\le 5$ ，字符串总长度 $\sum |S|\le 300000$ 。

题解

考虑用 $Manacher$ 算法进行回文串相关的统计。
不难发现，当且仅当我们当前的回文右边界进行扩展时，可能出现一个新的回文子串。
因为边界最多扩展 $|S|$ 次，所以最终答案 a n s ≤ min ⁡ { ∣ S ∣ } ans\le \min\{|S|\} ans≤min{∣S∣} ，我们可以枚举每一个公共回文子串进行验证，用 $Hash$ 进行字符串比较。
先对第一个字符串求出其所有的回文子串，然后枚举剩下的每一个字符串，保存共有的 $Hash$ 值。
$Hash$ 值可以存入 $set$ 中去重。
$Manacher$ 算法复杂度为 $O(n)$ ，使用 $set$ 去重复杂度 $O(logn)$ ，最终复杂度 $O(nlogn)$ ，可以通过此题。

注意点

在 $Manacher$ 预处理(夹入#以同时处理奇偶回文串)后的字符串上，每一个可以映射到原串上的回文串都以#结尾。
最后要除去单个#，因为它映射到原串上为空串。
注意防止 $Hash$ 碰撞，建议使用双模数。

参考代码

#include
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

const int MAXN=6e5+5,P1=1e9+7,P2=1e8+7,base=257;
int k;
set<long long>Set;
string s[MAXN];
int r[MAXN];
int pre1[MAXN],pre2[MAXN];
int pow1[MAXN],pow2[MAXN];

int get1(int l,int r){//获取模数1的区间Hash值
	return (pre1[r]-1ll*pre1[l-1]*pow1[r-l+1]%P1+P1)%P1;
}

int get2(int l,int r){//获取模数2的区间Hash值
	return (pre2[r]-1ll*pre2[l-1]*pow2[r-l+1]%P2+P2)%P2;
}

void init(){
	string S="@#";
	for(int i=0;i<s[1].length();++i){
		S+=s[1][i];
		S+="#";
	}
	S+="$";
	int l=S.length();
	pow1[0]=pow2[0]=1;
	for(int i=1;i+1<l;++i){//预处理模数的幂和前缀的Hash值
		pow1[i]=1ll*pow1[i-1]*base%P1;
		pow2[i]=1ll*pow2[i-1]*base%P2;
		pre1[i]=(1ll*pre1[i-1]*base+S[i])%P1;
		pre2[i]=(1ll*pre2[i-1]*base+S[i])%P2;
	}
	for(int i=1,mid=0,R=0;i+1<l;++i){//Manacher
		if(i<R)r[i]=min(R-i,r[2*mid-i]);
		else r[i]=0;
		while(S[i+r[i]]==S[i-r[i]]){
			if(S[i+r[i]]=='#')Set.insert(1ll*get1(i-r[i],i+r[i])*P2+get2(i-r[i],i+r[i]));
			//出现一个可能的新回文串,注意S[i+r[i]]=='#'
			++r[i];
		}
		if(i+r[i]>R){
			mid=i;
			R=i+r[i];
		}
	}
}

void work(string s){
	string S="@#";
	for(int i=0;i<s.length();++i){
		S+=s[i];
		S+="#";
	}
	S+="$";
	int l=S.length();
	pow1[0]=pow2[0]=1;
	for(int i=1;i+1<l;++i){
		pow1[i]=1ll*pow1[i-1]*base%P1;
		pow2[i]=1ll*pow2[i-1]*base%P2;
		pre1[i]=(1ll*pre1[i-1]*base+S[i])%P1;
		pre2[i]=(1ll*pre2[i-1]*base+S[i])%P2;
	}
	set<long long>_S;
	for(int i=1,mid=0,R=0;i+1<l;++i){
		if(i<R)r[i]=min(R-i,r[2*mid-i]);
		else r[i]=0;
		while(S[i+r[i]]==S[i-r[i]]){
			long long val=1ll*get1(i-r[i],i+r[i])*P2+get2(i-r[i],i+r[i]);
			if(S[i+r[i]]=='#'&&Set.count(val))_S.insert(val);//出现一个公共回文子串
			++r[i];
		}
		if(i+r[i]>R){
			mid=i;
			R=i+r[i];
		}
	}
	Set=_S;
}

int main()
{
	read(k);
	for(int i=1;i<=k;++i)cin>>s[i];
	init();
	for(int i=2;i<=k;++i)work(s[i]);
	cout<<Set.size()-1<<'\n';//去掉单个# 
	return 0;
}
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98