POJ 3974: Palindrome
题意：
最长回文子串的长度...
分析：
Manacher板子题...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
//眉眼如初，岁月如故 const int maxn=+; int cas,len,p[maxn]; char s[maxn],str[maxn]; inline void prework(void){
int i=;
for(i=;s[i];i++)
str[i*+]='#',str[(i+)*]=s[i];
len=i*+;str[]='$';str[len]=str[len+]='#';
} inline void manacher(void){
int id,mx=,ans=;
for(int i=;i<=len;i++){
p[i]=i<mx?min(mx-i,p[id*-i]):;
while(str[i+p[i]]==str[i-p[i]])
p[i]++;
if(p[i]+i>mx)
mx=p[i]+i,id=i;
if(ans<p[i]-)
ans=p[i]-;
}
printf("%d\n",ans);
} signed main(void){cas=;
while(scanf("%s",s)&&s[]!='E'){
printf("Case %d: ",++cas);
prework();manacher();
}
return ;
}//Cap ou pas cap. Pas cap.
HDU 3948: The Number of Palindromes
题意：
求原串中本质不同的子串个数...
分析：
写完发现大家都用的后缀数组...然而我不会...只能用Manacher+Hash水...
本质不同的回文串个数级别是O(n)的...所以我们可以暴力扫描回文串...我们枚举回文串的中心位置，然后判断最长回文串，如果没有出现过则判断其子串，否则直接break...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
#define int long long
#define II int
using namespace std;
//眉眼如初，岁月如故 const II maxn=+,Mod=; int l,cas,len,p[maxn],po[maxn],Hash[maxn]; char s[maxn],str[maxn]; struct M{
int hd[Mod+],nxt[maxn],w[][maxn],cnt; inline void clear(void){
memset(hd,-,sizeof(hd));cnt=;
} inline void insert(int x,int l,int r){
w[][cnt]=l,w[][cnt]=r,nxt[cnt]=hd[x],hd[x]=cnt++;
} inline bool find(int x,int l,int r){//cout<<"find"<<endl;cout<<l<<" "<<r<<endl;
for(int i=hd[x];i!=-;i=nxt[i])
if(r-l+==w[][i]-w[][i]+){
int j;
for(j=;j<=r-l+;j++)
if(str[w[][i]+j-]!=str[w[][i]+j-])
break;
if(j==r-l+)//{
return true;//cout<<"finish find"<<endl;}
}//cout<<"finish find"<<endl;
return false;
} }mp; inline void prework(void){
int i=;l=strlen(s);
for(i=;s[i];i++)
str[i*+]='#',str[(i+)*]=s[i];
len=i*+;str[]='$';str[len]=str[len+]='#';
for(int i=;i<=len;i++){
if(str[i]>='a'&&str[i]<='z')
Hash[i]=(Hash[i-]*%Mod+str[i]-'a'+)%Mod;
else
Hash[i]=(Hash[i-]*%Mod+)%Mod;
}
} inline void manacher(void){
int id,mx=;
for(int i=;i<=len;i++){
p[i]=i<mx?min(mx-i,p[(id<<)-i]):;
while(str[p[i]+i]==str[i-p[i]])
p[i]++;
if(i+p[i]>mx)
mx=i+p[i],id=i;
}
} inline void find(void){
int ans=;
for(int i=;i<=len;i++){//cout<<i<<" "<<p[i]<<endl;
if(!mp.find((Hash[i+p[i]-]-Hash[i-]*po[p[i]]%Mod+Mod)%Mod,i,i+p[i]-)){
ans++,mp.insert((Hash[i+p[i]-]-Hash[i-]*po[p[i]]%Mod+Mod)%Mod,i,i+p[i]-);
int lala=p[i]-;
while(lala>=&&!mp.find((Hash[i+lala-]-Hash[i-]*po[lala]%Mod+Mod)%Mod,i,i+lala-))
ans++,mp.insert((Hash[i+lala-]-Hash[i-]*po[lala]%Mod+Mod)%Mod,i,i+lala-),lala-=;
}
}
printf("%lld\n",ans-);
} signed main(void){
scanf("%lld",&cas);po[]=;Hash[]=;
for(int i=;i<=;i++)
po[i]=po[i-]*%Mod;
for(int i=;i<=cas;i++){mp.clear();
scanf("%s",s);printf("Case #%lld: ",i);
prework();manacher();find();
}
return ;
}//Cap ou pas cap. Pas cap.
By NeighThorn