URAL 2040 （回文自动机）

时间：2022-05-30 02:41:34

Problem Palindromes and Super Abilities 2 （URAL2040）

题目大意

　　给一个字符串，从左到右依次添加，询问每添加一个字符，新增加的回文串数量。

解题分析

　　用回文自动机来做，如果新添加了一个字符，自动机中新开了一个节点，说明新增加了一个回文串。

　　对于每新添加一个字符，新增加的回文串数量最多为1。

　　另外，这道题既卡空间又卡时间，交了n发才过。

参考程序

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <string>

 #include <vector>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #pragma comment(linker,"/STACK:102400000,102400000")

 using namespace std;

 #define     N             5000008

 #define     V             1008

 #define        E            60008

 #define        lson        l,m,rt<<1

 #define     rson        m,r+1,rt<<1|1

 #define        clr(x,v)    memset(x,v,sizeof(x));

 #define        LL            long long 

 const int    mo    =    ;

 const int     inf =    0x3f3f3f3f;

 const int     INF =    ;

 /**************************************************************************/

 int n,cnt,last;

 int nt[N][],size[N],len[N],fail[N];

 char s[N];

 void init(){

     fail[]=fail[]=;

     len[]=-;

     last=; cnt=;

 }

 void insert(int c,int n){

     int p=last;

     while (s[n-len[p]-]!=s[n]) p=fail[p];

     if (!nt[p][c]){

         int now=++cnt,k=fail[p];

         len[now]=len[p]+;

         while (s[n-len[k]-]!=s[n]) k=fail[k];

         fail[now]=nt[k][c]; nt[p][c]=now;

         putchar('');

     }

     else putchar("");

     last=nt[p][c];

     size[last]++;

 }

 void solve(){

     for (int i=cnt;i>=;i--) size[fail[i]]+=size[i];

 }

 int main(){

     gets(s+);

     init();

     n=strlen(s+);

     for (int i=;i<=n;i++) insert(s[i]-,i);

 }

相关文章