题解 P3449 【[POI2006]PAL-Palindromes】
SovietPower✨
2017-08-08 20:52:18
//学的不久，仅个人理解，可能不对，有错请指出
若要两个回文串相连后仍是回文串，那回文串 si一定是 sj(leni<=lenj)的循环节(可以相等，每个回文串自己+自己肯定是个回文串)
是循环节也就是是前缀
先用Trie树得出一个串上每个点的前缀情况，再通过Hash判断是否为其循环节
这样得出所有 len[i]<=len[j]的满足条件的(si,sj),同样也有(sj,si)
so 答案再\*2 ，但是每个(i,i)仅有一个，这样有n个在res\*2时多了n，so res = res\*2-n
另对于Hash判断循环节，若i是j的循环节，满足：
Hash[i]\* p^len[j]+Hash[j] == Hash[j]\* p^len[i]+Hash[i]
设字串i为abc，母串j为abcabc，选的Hash进制为p
Hash[i](len=3) = ((0+a)p+b)p+c = ap2+bp+c (数字均为次数)
Hash[j](len=6) = (((((0+a)p+b)p+c)p+a)p+b)p+c = ap5+bp4+cp3+ap2+bp+c
现令 x = Hash[i]\* Base^len[j] + Hash[j] = I\*p^6 + J
y = Hash[j]\* Base^len[i] + Hash[i] = J\*p^3 + I
可得 x = y = ap8+bp7+cp6+ap5+bp4+cp3+ap2+bp+c
(一推就出)
非指针版 817ms 290640kb 内存比较。。
```cpp
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2000005,base=233;
typedef unsigned long long ull;
int n,len[N],t[N][27],sz,val[N],belong[N];
//belong[i]:i这个节点属于哪个串的
//注意总长不会超过N，即节点数也不会超过N
//val[N*27] 过大导致一直RE。。
ull p[N],Hash[N];
string s[N];
char tmp[N];
inline int read()
{
int now=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar())
if(c=='-') f=-1;
for(;isdigit(c);c=getchar())
now=(now<<3)+(now<<1)+c-'0';
return now*f;
}
void Pre()
{
p[0]=1;
for(int i=1;i<=2000000;++i)
p[i]=p[i-1]*base;
}
int main()
{
Pre();
n=read();
for(int i=1;i<=n;++i)
{
len[i]=read();
scanf("%s",tmp);s[i]=tmp;//这样读string会快
// TLE:cin>>tmp;
int u=0;
ull v=0;
for(int j=0;j<len[i];++j)
{
int id=s[i][j]-'a';
if(!t[u][id])
t[u][id]=++sz;
u=t[u][id];
v=v*base+(ull)(id+1);
}
++val[u],belong[u]=i,Hash[i]=v;
}
long long res=0;
for(int i=1;i<=n;++i)
{
int u=0;
for(int j=0;j<len[i];++j)
{
u=t[u][s[i][j]-'a'];
if(val[u] && Hash[belong[u]]*p[len[i]]+Hash[i]==Hash[i]*p[len[belong[u]]]+Hash[belong[u]])
res+=val[u];
}
}
printf("%lld",res*2-n);
return 0;
}
```
指针版 优化内存 941ms 101609kb
```cpp
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2000005,base=233;
typedef unsigned long long ull;
int n,len[N];
struct Node
{
int val,belong;
Node *nxt[27];
Node()
{
val=0;memset(nxt,NULL,sizeof nxt);
}
};
Node *root=new Node();
Node *rt;
ull p[N],Hash[N];
string s[N];
char tmp[N];
inline int read()
{
int now=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar())
if(c=='-') f=-1;
for(;isdigit(c);c=getchar())
now=(now<<3)+(now<<1)+c-'0';
return now*f;
}
void Pre()
{
p[0]=1;
for(int i=1;i<=2000000;++i)
p[i]=p[i-1]*base;
}
int main()
{
Pre();
n=read();
for(int i=1;i<=n;++i)
{
len[i]=read();
scanf("%s",tmp);s[i]=tmp;//这样读string会快
// TLE:cin>>tmp;
rt=root;
ull v=0;
for(int j=0;j<len[i];++j)
{
int id=s[i][j]-'a';
if(rt->nxt[id]==NULL)
rt->nxt[id]=new Node();
rt=rt->nxt[id];
v=v*base+(ull)(id+1);
}
++rt->val,rt->belong=i,Hash[i]=v;
}
long long res=0;
for(int i=1;i<=n;++i)
{
rt=root;
for(int j=0;j<len[i];++j)
{
rt=rt->nxt[s[i][j]-'a'];
if(rt->val && Hash[rt->belong]*p[len[i]]+Hash[i]==Hash[i]*p[len[rt->belong]]+Hash[rt->belong])
res+=rt->val;
}
}
printf("%lld",res*2-n);
return 0;
}
```