BZOJ3676: [Apio2014]回文串

PAM裸题

关于PAM怎么构造我之前有个链接

然后就是每次加num就好了

最后统计一下

我打的代码常数打的吓人

PAM:

#include<cstdio>
#include<iostream>
#include<cstring>
using  namespace std;

struct Node
{
  int len;
  Node *ch[];
  Node *last;
  int num;
  Node(){for(len=;len<=;len++)ch[len]=NULL;last=NULL;len=num=;}
};
Node*Max_Node,*Node_2,*Node_1;
int num;
Node *Stack[];
int top;
inline Node *New_Node()
{
    Node *res=new Node;
    Stack[top++]=res;
    return res;
}
char s[];
inline void begin(){Node_2=new Node;Node_1=new Node;Max_Node=Node_2;num=;Node_2->last=Node_1->last=Node_1;Node_1->len=-;Node_2->len=;}
inline bool add(int place)
{
    bool Exit=false;
    Node *cur=Max_Node;
    int curlen=,son=s[place]-'a';
    while(true)
      {
         curlen=cur->len;
         if(place--curlen>=&&s[place--curlen]==s[place])
             break;
          cur=cur->last;
      }
    if(cur->ch[son])
         Max_Node=cur->ch[son],cur->ch[son]->num++; 
    else
     {
         Exit=true;
         Node*tp=New_Node();
         Max_Node=tp;
         tp->len=cur->len+;
         cur->ch[son]=tp;
         if(tp->len==)
            tp->last=Node_2,tp->num=;
         else
          {
             while(true)
                {
                    cur=cur->last;
                    curlen=cur->len;
                    if(place--curlen>=&&s[place--curlen]==s[place])
                      {
                        Max_Node->last=cur->ch[son];
                        break;
                      }
                }
            Max_Node->num=;             
          }  
    }
    return Exit;
}

long long ans=-;
inline void Calc()
{
    Node *tp;
    for(int i=top-;i!=-;i--)
      {
        tp=Stack[i];tp->last->num+=tp->num;
        ans=max(ans,tp->num*l*tp->len);
      }
}
char c;
int main()
{
    int len=;
    do c=getchar();while(c<'a'||c>'z');
    while(c<='z'&&c>='a')
       s[len++]=c,c=getchar();
    begin();
    for(int i=;i<len;i++)add(i);
    Calc();
    printf("%lld\n",ans);
    return ;
} 
           

还有一种方法很丑 是用manacher+SAM我不想打= =