Manacher

HDU 3068 Manacher裸题

 1 #include <cstdio>
 2 #include <cstring>
 3 const int Maxn=110100;
 4 char Str[Maxn<<1],STR[Maxn<<1];
 5 int Len,x,P[Maxn<<1],Id,Mx;
 6 inline int Max(int x,int y) {return x>y?x:y;}
 7 inline int Min(int x,int y) {return x>y?y:x;}
 8 inline Init()
 9 {
10     Len=strlen(Str+1);
11     for (int i=1;i<=Len;i++) STR[i]=Str[i];
12     Str[0]='$'; Str[1]='#';
13     for (int i=1;i<=Len;i++) Str[i<<1]=STR[i],Str[i<<1|1]='#';
14     Len=Len<<1|1; Id=1;Mx=0;
15 }
16 inline int Manacher()
17 {
18     for (int i=2;i<=Len;i++)
19     {
20         if (Mx>i) P[i]=Min(P[2*Id-i],Mx-i); else P[i]=1;
21         while (Str[i+P[i]]==Str[i-P[i]]) P[i]++;
22         if (i+P[i]>Mx) Mx=P[i]+i,Id=i;
23     }
24     int Ret=0;
25     for (int i=1;i<=Len;i++)  Ret=Max(Ret,P[i]);
26     return Ret-1;
27 }
28 int main()
29 {
30     while (scanf("%s",Str+1)!=EOF)
31     {
32         Init();
33         printf("%d
",Manacher());
34     }
35     return 0;
36 }

C++

BZOJ 3790 线段求交

用Manacher把最大的回文半径求出然后线段求交即可

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <vector>
 6 #define mp make_pair
 7 #define pb push_back
 8 #define PA pair<int,int>
 9 #define fi first
10 #define se second
11 using namespace std;
12 const int Maxn=200010;
13 const int Inf=0x3f3f3f3f;
14 char S[Maxn],Str[Maxn];
15 int P[Maxn],c[Maxn];
16 int Len;
17 vector<PA> Line;
18 inline int Min(int x,int y) {return x>y?y:x;}
19 inline int lowbit(int x) {return x&-x;}
20 inline int Query(int x)
21 {
22     if (x==0) return 0;
23     int Ret=Inf;
24     for (int i=x;i<=Len;i+=lowbit(i))    Ret=Min(Ret,c[i]);
25     return Ret;
26 }
27 inline void Update(int x,int y)
28 {
29     for (int i=x;i;i-=lowbit(i)) c[i]=Min(c[i],y);
30 }
31 inline void Manacher()
32 {
33     int m=Len<<1|1;
34     for (int i=1;i<=Len;i++)
35     {
36         S[i<<1]=Str[i];
37         S[i<<1|1]='#';
38     } 
39     S[1]='#'; S[0]='&'; S[m+1]='^';
40     int Mx=0,Id=0;
41     for (int i=1;i<=m;i++)
42     {
43         if (i<Mx) P[i]=Min(Mx-i,P[2*Id-i]); else P[i]=1;
44         while (S[i-P[i]]==S[i+P[i]]) P[i]++;
45         if (i+P[i]>Mx) Mx=i+P[i],Id=i;
46         int l=(i-P[i])/2+1,r=(i+P[i])/2-1;
47         if (l<=r) Line.pb(mp(r,l));
48     }
49 }
50 int main()
51 {
52     while (scanf("%s",Str+1)!=EOF)
53     {
54         Len=strlen(Str+1); Line.clear();
55         Manacher(); 
56         sort(Line.begin(),Line.end());
57         for (int i=0;i<=Len;i++) c[i]=Inf;
58         int Ans=Inf;
59         for (int i=0;i<Line.size();i++)
60         {
61             int x=Query(Line[i].se-1)+1;
62             Update(Line[i].fi,x);
63             if (Line[i].fi==Len) Ans=Min(Ans,x);
64         }
65         printf("%d
",Ans-1);
66     }
67     return 0;
68 }

C++