题解 P3449 【[POI2006]PAL-Palindromes】
Baihua
2019-06-24 17:55:02
### 【题解】[POI2006]PAL-Palindromes
* [题目地址](https://www.luogu.org/problemnew/show/P3449)
---
思路：
* 回文串和自己相加仍是回文串。
* 当$S[i]$是$S[j]$的前缀时，$S[i]+S[j]$可能构成回文串。
* 对于$S[i]$，利用$Trie$获得是$S[i]$的前缀的字符串。再利用字符串的$Hash$判断是否回文。
* 知道前串的长度、两串的散列值，就可以获得两串连接后的散列值。如下：
* ```c++
HashLink = HashValue[Left] * HashPow[Right.Length] + HashValue[Left]
```
下面是部分代码（头文件省略）。
* 把字符串加入字典树，并且计算$Hash$值和长度。
```c++
int Add (int From ) {
int P = 0 ,R = 1 ;
unsigned long long int NowHash = 0 , NowLen = 0;
for (int i = From ; S[i] != '0' ; ++ i) {
if (!T[P][S[i] - 'a']) T[P][S[i] - 'a'] = ++ Tot;
P = T[P][S[i] - 'a'] ;
++ R;
NowHash = NowHash * HashBase + S[i] ;
++ NowLen ;
}
++ End[P] ;
Len[P] = NowLen , HashValue[P] = NowHash ;
return From + R ;
}
```
* 对于每一个字符串，枚举它的前缀，并且判断$Hash(Left + Right) == Hash(Right + Left)$。如果成立，那将对答案贡献2。
* ```c++
void Ask (int P , int Now , int E ) {
if (Now > E) {
NowP = P ;
return ;
}
Ask (T[P][S[Now] - 'a'] , Now + 1 , E ) ;
if (End[P]) {
if (HashValue[NowP] * HashPow[Len[P]] + HashValue[P] == HashValue[P] * HashPow[Len[NowP]] + HashValue[NowP]) {
Ans += 2 ;
if (P == NowP) -- Ans ;
}
}
}
```
* 最后，每个字符串和自己可以连接。
* 完整代码：
```c++
#include <stdio.h>
#include <string.h>
#define Clean(X,K) memset(X,K,sizeof(X))
using namespace std ;
#include <iostream>
const int Maxn = 2000005 , Base = 26 ;
int N , Tail = 0 , T[Maxn][Base] , End[Maxn] , Tot = 0 , Len[Maxn];
unsigned long long HashValue[Maxn] , HashBase = 17 , HashPow[Maxn] = {1} , Ans = 0;
char S[Maxn * 2] , Tmp[Maxn];
int Add (int From ) {
int P = 0 ,R = 1 ;
unsigned long long int NowHash = 0 , NowLen = 0;
for (int i = From ; S[i] != '0' ; ++ i) {
if (!T[P][S[i] - 'a']) T[P][S[i] - 'a'] = ++ Tot;
P = T[P][S[i] - 'a'] ;
++ R;
NowHash = NowHash * HashBase + S[i] ;
++ NowLen ;
}
++ End[P] ;
Len[P] = NowLen , HashValue[P] = NowHash ;
return From + R ;
}
int NowP ;
void Ask (int P , int Now , int E ) {
if (Now > E) {
NowP = P ;
return ;
}
Ask (T[P][S[Now] - 'a'] , Now + 1 , E ) ;
if (End[P]) {
if (HashValue[NowP] * HashPow[Len[P]] + HashValue[P] == HashValue[P] * HashPow[Len[NowP]] + HashValue[NowP]) {
Ans += 2 ;
if (P == NowP) -- Ans ;
}
}
}
int main () {
// freopen ("P3449.in" , "r" , stdin) ;
Clean (T , 0) , Clean (End , 0) , Clean (Len , 0);
scanf ("%d" , &N) ;
for (int i = 1 ; i <= N; ++ i) {
int L ;
scanf ("%d " , &L) ;
scanf ("%s" , Tmp) ;
for (int j = 0 ; j < L; ++ j) S[Tail + j] = Tmp[j] ;
Tail += L ;
S[Tail++] = '0' ;
}
-- Tail ;
int Now = 0 , Cnt = -1;
while (Now <= Tail) Now = Add (Now) ;
for (int i = 1 ; i < Maxn ; ++ i) HashPow[i] = HashPow[i - 1] * HashBase ;
int Lst = 0 ;
Cnt = -1 ;
for (int i = 1 ; i <= Tail ; ++ i)
if (S[i] == '0') {
Ask (0 , Lst , i - 1) ;
Lst = i + 1 ;
}
cout << Ans + N<<endl;
fclose (stdin) , fclose (stdout) ;
return 0 ;
}
```