hdu 5421 Victor and String
支持双端插入的回文树。
考虑维护第二个 last 表示当前整个串的最长回文前缀。
往前 append 的时候可以直接那第二个 last 来跳 fail ， 因为回文前缀和回文后缀是对称的。只有 getfail 的时候需要改一下，变成判断当前字符和前缀之后的字符是否相同。
还要注意，如果当前的前面/后面 的 last 是整个串，那么需要把另一个 last 也设置成整个串。
注意如果当前插入得到的回文串pam里面已经有了也要加上它的贡献！
cpp1
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
| #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 300006
int n;
struct pam {
int son[MAXN][26] , fail[MAXN] , dep[MAXN] , len[MAXN] , s[MAXN * 3];
int last[2] , n = 0 , st = 100006 , en = st , p = 0; long long re = 0;
int newnode(int l) {
for (int i = 0; i < 26; i++)
son[p][i] = 0;
len[p] = dep[p] = l;
return p++;
}
void init( ) {
memset( s , -1 , sizeof s );
p = re = 0;
newnode( 0 ) , newnode( -1 );
st = en = 100006;
last[0] = last[1] = n = 0;
fail[0] = 1;
}
int getfail1( int u ) {
while( s[en - len[u] - 1] != s[en] ) u = fail[u];
return u;
}
int getfail2( int u ) {
while( s[st + len[u] + 2] != s[st + 1] ) {
u = fail[u];
}
return u;
}
void add( int u , bool af ) {
u -= 'a';
int cur;
if( af ) {
s[++ en] = u;
cur = getfail1( last[af] );
}
else s[st --] = u , cur = getfail2( last[af] );
if( !son[cur][u] ) {
int now = newnode( len[cur] + 2 );
fail[now] = son[af ? getfail1(fail[cur]) : getfail2(fail[cur])][u];
son[cur][u] = now;
dep[now] = dep[fail[now]] + 1 , re += dep[now];
} else re += dep[son[cur][u]];
last[af] = son[cur][u];
if( len[last[af]] == en - st ) last[af^1] = last[af];
}
int dif( ) {
return p - 2;
}
long long und( ) {
return re;
}
} pam ;
int main() {
int op; char ch[3];
while( cin >> n ) {
pam.init();
while( n -- ) {
scanf("%d",&op);
if( op == 1 ) {
scanf("%s",ch) , pam.add( ch[0] , 0 );
} else if( op == 2 ) {
scanf("%s",ch) , pam.add( ch[0] , 1 );
} else if( op == 3 ) {
printf("%d\n",pam.dif( ));
} else printf("%lld\n" , pam.und());
}
}
}
|
