Kuangbin_K&Z&M_T题(POJ-3376)

发表于 |

题目描述：n个串，两两连接，有多少种方案形成回文串
枚举每个串作为连接后较长的串，找到所有回文前缀，剩余的后缀部分的反串连在当前串前面可得回文串，跑字典树即可。再找到所有回文后缀，剩余的前缀部分的反串连在当前串后面也可得回文串，跑反串字典树即可。还有一种是两个串长度相等，放入之前的任意一种情况都行。本题卡常，用string会T，建立两棵字典树会mle，所以要用一个字符数组模拟n个串，并先做第一种，然后清空字典树并重建反串字典树再做第二种。 

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/*
 *powered by caibiCH2
 *create at 2019-09-29 23:24:39
 */
//#pragma GCC optimize(2)
#include<poj专用万能头文件>

#define elif else if
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define INF 0x3f3f3f3f
typedef long long ll;

using namespace std;

typedef unsigned pnt;

const char ori='a';
struct trie{
	struct node{
		int num;
		pnt next[26];
	}data[2000100];
	pnt l;
	
	void init(){memset(this,0,sizeof(*this));}
	
	void append(const char s[],const int&len){
		pnt now=0;
		for(pnt i=0;i<len;++i){
			if(!data[now].next[s[i]-ori]){
				data[now].next[s[i]-ori]=++l;
			}
			now=data[now].next[s[i]-ori];
		}
		++data[now].num;
	}
	
}st;
char s1[5001000];
void manacher_init(const char s[],const int&l){
	s1[0]='#';
	for(int i=0;i<l;i+=1){
		s1[(i<<1)+1]=s[i];
		s1[(i<<1)+2]='#';
	}
}

vector<int>manacher(const char s[],int l){
	manacher_init(s,l);
	l+=l+1;
	vector<int>p(l);
	int now=0,mx=0;
	for(int i=0;i<l;i+=1){
		if(i<mx)p[i]=min(p[2*now-i],mx-i);
		else p[i]=1;
		while(i-p[i]>=0&&i+p[i]<l&&s1[i-p[i]]==s1[i+p[i]])++p[i];
		if(mx<i+p[i])now=i,mx=i+p[i];
	}
	return p;
}
inline void read(int &x){
	int f=1;x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while('0'<=ch&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
int len[2001000];
int sta[2001000];
char s[2001000],c[2001000];
int main (/*int argc, char const* argv[]*/){
//	std::ios::sync_with_stdio(false);
//	std::cin.tie(0);
	int n;read(n);
	for(int i=1;i<=n;i+=1){
		read(len[i]);
		sta[i+1]=sta[i]+len[i];
		scanf("%s",s+sta[i]);
		st.append(s+sta[i],len[i]);
	}
	ll ans=0;
	for(int i=1;i<=n;i+=1){
		ll c=0;
		vector<int>m=manacher(s+sta[i],len[i]);
		int l=len[i];
		for(int t=l,now=0;t>0;){
			if(m[t]==t+1)c+=st.data[now].num;
			--t;
			if(t<=0)break;
			now=st.data[now].next[(s+sta[i])[t]-ori];
			if(!now)break;
		}
		ans+=c;
	}
	st.init();
	for(int i=1;i<=n;i+=1){
		strncpy(c,s+sta[i],len[i]);
		reverse(c,c+len[i]);
		st.append(c,len[i]);
	}
	for(int i=1;i<=n;i+=1){
		ll c=0;
		vector<int>m=manacher(s+sta[i],len[i]);
		int l=len[i];
		for(int t=l,now=0;t<=m.size();){
			if(m[t]==m.size()-t)c+=st.data[now].num;
			++t;
			if(t>=m.size())break;
			now=st.data[now].next[(s+sta[i])[t-l-1]-ori];
			if(!now)break;
		}
		ans+=c;
	}
	cout<<ans<<'\n';
	return 0;
}