Palindromes and Super Abilities

Problem's Link:

Mean:

给你一个长度为n的字符串S，输出S的各个前缀中回文串的数量。

analyse:

回文树(回文自动机)的模板题。

由于回文自动机中的p是一个计数器，也相当于一个指针，记录的是当前插入字符C后回文树中有多少个节点。

那么我们只需要一路插，一路输出p-2就行。

p-2是因为一开始回文树中就有两个节点。这是两个根节点，分别是长度为偶数和奇数的回文串的根节点。

Time complexity: O(N)

Source code:

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-17-14.58
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define  LL long long
#define  ULL unsigned long long
using
namespace
std; 
const
int
MAXN
=
100005 ; 
const
int N 
=
26 ; 
char s 
[
MAXN
];
namespace
Palindromic_Tree
{ 
int
next
[
MAXN
][N 
] ; 
//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成
int
fail
[
MAXN
] ; 
//fail指针，失配后跳转到fail指针指向的节点
int
cnt
[
MAXN
] ; 
int
num
[
MAXN
] ; 
int
len
[
MAXN
] ; 
//len[i]表示节点i表示的回文串的长度
int S 
[
MAXN
] ; 
//存放添加的字符
int
last ; 
//指向上一个字符所在的节点，方便下一次add
int n ; 
//字符数组指针
int p ; 
//节点指针
int
newnode( 
int
l)     
//新建节点
{ 
for( 
int
i
=
0 ; 
i
< N ; 
++
i) 
next
[p 
][
i
]
=
0 ; 
cnt
[p 
]
=
0 ; 
num
[p 
]
=
0 ; 
len
[p 
]
=
l ; 
return p 
++ ; 
}
void
init()   
//初始化
{ 
            p 
=
0 ; 
newnode( 
0) ; 
newnode( 
-
1) ; 
last
=
0 ; 
            n 
=
0 ; 
            S 
[n 
]
=
-
1 ; 
//开头放一个字符集中没有的字符，减少特判
fail
[
0
]
=
1 ; 
}
int
get_fail( 
int
x)     
//和KMP一样，失配后找一个尽量最长的
{ 
while(S 
[n 
-
len
[
x
]
-
1
]
!= S 
[n 
])
x
=
fail
[
x
] ; 
return
x ; 
}
void
add( 
int
c) 
{ 
c
-=
'a' ; 
            S 
[
++ n 
]
=
c ; 
int
cur
=
get_fail( 
last) ;   
//通过上一个回文串找这个回文串的匹配位置
if( 
!
next
[
cur
][
c
])
//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
{ 
int
now
=
newnode( 
len
[
cur
]
+
2) ;   
//新建节点
fail
[
now
]
=
next
[
get_fail( 
fail
[
cur
])][
c
] ;   
//和AC自动机一样建立fail指针，以便失配后跳转
next
[
cur
][
c
]
=
now ; 
num
[
now
]
=
num
[
fail
[
now
]]
+
1 ; 
}
last
=
next
[
cur
][
c
] ; 
cnt
[
last
]
++ ; 
}
void
Count() 
{ 
for( 
int
i
= p 
-
1 ; 
i
>=
0 ; 
--
i) 
cnt
[
fail
[
i
]]
+=
cnt
[
i
] ; 
//父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
}
} ; 
using
namespace
Palindromic_Tree; 
int
main() 
{ 
ios_base
::
sync_with_stdio( 
false); 
cin
.
tie( 
0); 
while( 
~
scanf( 
"%s"
,s)) 
{ 
init(); 
for( 
int
i
=
0;s 
[
i
];
++
i) 
{ 
add(s 
[
i
]);
printf( 
i
==
0
?
"%d"
:
" %d"
,p 
-
2); 
}
puts( 
""); 
//            Count();
}
return
0; 
}
/*
*/

代码2：

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-17-16.51
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define  LL long long
#define  ULL unsigned long long
using
namespace
std; 
const
int
MAXN
=
100010; 
struct
node
{ 
int
next
[
26
];
int
len; 
int
sufflink; 
int
num; 
};
int
len; 
char s 
[
MAXN
];
node
tree
[
MAXN
];
int
num; 
// node 1 - root with len -1, node 2 - root with len 0
int
suff; 
// max suffix palindrome
long
long
ans; 
bool
addLetter( 
int
pos) 
{ 
int
cur
=
suff
,
curlen
=
0; 
int
let
= s 
[
pos
]
-
'a'; 
while( 
true) 
{ 
curlen
=
tree
[
cur
].
len; 
if( 
pos
-
1
-
curlen
>=
0
&&s 
[
pos
-
1
-
curlen
]
==s 
[
pos
])
break; 
cur
=
tree
[
cur
].
sufflink; 
}
if( 
tree
[
cur
].
next
[
let
])
{ 
suff
=
tree
[
cur
].
next
[
let
];
return
false; 
}
suff
=
++
num; 
tree
[
num
].
len
=
tree
[
cur
].
len
+
2; 
tree
[
cur
].
next
[
let
]
=
num; 
if( 
tree
[
num
].
len
==
1) 
{ 
tree
[
num
].
sufflink
=
2; 
tree
[
num
].
num
=
1; 
return
true; 
}
while( 
true) 
{ 
cur
=
tree
[
cur
].
sufflink; 
curlen
=
tree
[
cur
].
len; 
if( 
pos
-
1
-
curlen
>=
0
&& s 
[
pos
-
1
-
curlen
]
== s 
[
pos
])
{ 
tree
[
num
].
sufflink
=
tree
[
cur
].
next
[
let
];
break; 
}
}
tree
[
num
].
num
=
1
+
tree
[
tree
[
num
].
sufflink
].
num; 
return
true; 
}
void
initTree() 
{ 
num
=
2; 
suff
=
2; 
tree
[
1
].
len
=
-
1; 
tree
[
1
].
sufflink
=
1; 
tree
[
2
].
len
=
0; 
tree
[
2
].
sufflink
=
1; 
}
int
main() 
{ 
scanf( 
"%s"
,s); 
len
=
strlen(s); 
initTree(); 
for( 
int
i
=
0; 
i
<
len; 
i
++) 
{ 
addLetter( 
i); 
printf( 
i
==
0
?
"%d"
:
" %d"
,
num
-
2); 
//            ans += tree[suff].num;
}
putchar( 
10); 
//       cout << ans << endl;
return
0; 
}