Manacher--雾窗寒对遥天暮，暮天遥对寒窗雾

POJ 3974: Palindrome

题意：

最长回文子串的长度...

分析：

Manacher板子题...

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
//眉眼如初，岁月如故 

const int maxn=2000000+5;

int cas,len,p[maxn];

char s[maxn],str[maxn];

inline void prework(void){
    int i=0;
    for(i=0;s[i];i++)
        str[i*2+1]='#',str[(i+1)*2]=s[i];
    len=i*2+1;str[0]='$';str[len]=str[len+1]='#';
}

inline void manacher(void){
    int id,mx=0,ans=0;
    for(int i=1;i<=len;i++){
        p[i]=i<mx?min(mx-i,p[id*2-i]):1;
        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]-1)
            ans=p[i]-1;
    }
    printf("%d
",ans);
}

signed main(void){cas=0;
    while(scanf("%s",s)&&s[0]!='E'){
        printf("Case %d: ",++cas);
        prework();manacher();
    }
    return 0;
}//Cap ou pas cap. Pas cap.

HDU 3948: The Number of Palindromes

题意：

求原串中本质不同的子串个数...

分析：

写完发现大家都用的后缀数组...然而我不会...只能用Manacher+Hash水...

本质不同的回文串个数级别是O(n)的...所以我们可以暴力扫描回文串...我们枚举回文串的中心位置，然后判断最长回文串，如果没有出现过则判断其子串，否则直接break...

代码：

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 //by NeighThorn
 6 #define int long long
 7 #define II int
 8 using namespace std;
 9 //眉眼如初，岁月如故 
10 
11 const II maxn=200000+5,Mod=23333333;
12 
13 int l,cas,len,p[maxn],po[maxn],Hash[maxn]; 
14 
15 char s[maxn],str[maxn];
16 
17 struct M{
18     int hd[Mod+10],nxt[maxn],w[2][maxn],cnt;
19     
20     inline void clear(void){
21         memset(hd,-1,sizeof(hd));cnt=0;
22     }
23     
24     inline void insert(int x,int l,int r){
25         w[0][cnt]=l,w[1][cnt]=r,nxt[cnt]=hd[x],hd[x]=cnt++;
26     }
27     
28     inline bool find(int x,int l,int r){//cout<<"find"<<endl;cout<<l<<" "<<r<<endl;
29         for(int i=hd[x];i!=-1;i=nxt[i])
30             if(r-l+1==w[1][i]-w[0][i]+1){
31                 int j;
32                 for(j=1;j<=r-l+1;j++)
33                     if(str[w[0][i]+j-1]!=str[w[0][i]+j-1])
34                         break;
35                 if(j==r-l+2)//{
36                     return true;//cout<<"finish find"<<endl;}
37             }//cout<<"finish find"<<endl;
38         return false;
39     }
40     
41 }mp;
42 
43 inline void prework(void){
44     int i=0;l=strlen(s);
45     for(i=0;s[i];i++)
46         str[i*2+1]='#',str[(i+1)*2]=s[i];
47     len=i*2+1;str[0]='$';str[len]=str[len+1]='#';
48     for(int i=1;i<=len;i++){
49         if(str[i]>='a'&&str[i]<='z')
50             Hash[i]=(Hash[i-1]*27%Mod+str[i]-'a'+1)%Mod;
51         else
52             Hash[i]=(Hash[i-1]*27%Mod+27)%Mod;
53     }
54 }
55 
56 inline void manacher(void){
57     int id,mx=0;
58     for(int i=1;i<=len;i++){
59         p[i]=i<mx?min(mx-i,p[(id<<1)-i]):1;
60         while(str[p[i]+i]==str[i-p[i]])
61             p[i]++;
62         if(i+p[i]>mx)
63             mx=i+p[i],id=i;
64     }
65 }
66 
67 inline void find(void){
68     int ans=0;
69     for(int i=1;i<=len;i++){//cout<<i<<" "<<p[i]<<endl;
70         if(!mp.find((Hash[i+p[i]-1]-Hash[i-1]*po[p[i]]%Mod+Mod)%Mod,i,i+p[i]-1)){
71             ans++,mp.insert((Hash[i+p[i]-1]-Hash[i-1]*po[p[i]]%Mod+Mod)%Mod,i,i+p[i]-1);
72             int lala=p[i]-2;
73             while(lala>=1&&!mp.find((Hash[i+lala-1]-Hash[i-1]*po[lala]%Mod+Mod)%Mod,i,i+lala-1))
74                 ans++,mp.insert((Hash[i+lala-1]-Hash[i-1]*po[lala]%Mod+Mod)%Mod,i,i+lala-1),lala-=2;
75         }
76     }
77     printf("%lld
",ans-1);
78 }
79 
80 signed main(void){
81     scanf("%lld",&cas);po[0]=1;Hash[0]=0;
82     for(int i=1;i<=100000;i++)
83         po[i]=po[i-1]*27%Mod;
84     for(int i=1;i<=cas;i++){mp.clear();
85         scanf("%s",s);printf("Case #%lld: ",i);
86         prework();manacher();find();
87     }
88     return 0;
89 }//Cap ou pas cap. Pas cap.

By NeighThorn