bzoj千题计划304：bzoj3676: [Apio2014]回文串

2021-04-18 20:25

阅读：544

标签：fine span void 分享 using tps AC 回文串 geo

https://www.lydsy.com/JudgeOnline/problem.php?id=3676

回文自动机模板题

4年前的APIO如今竟沦为模板，技术分享图片，，╮(╯▽╰)╭，唉

#include
#include
#include

using namespace std;

#define N 300001

char ss[N];
int s[N];

int tot=1,last;
int fail[N],len[N],cnt[N];
int tr[N][26];
int p,c,np,t;


void extend(int i)
{
    p=last; c=s[i];
    while(s[i-1-len[p]]!=c) 
        p=fail[p];
    if(!tr[p][c])
    {
        np=++tot;
        len[np]=len[p]+2;
        t=fail[p];
        while(s[i-1-len[t]]!=c) t=fail[t];
        fail[np]=tr[t][c];
        tr[p][c]=np;
    }
    else np=tr[p][c];
    cnt[last=np]++;
}

int main()
{
    scanf("%ss",ss+1);
    int n=strlen(ss+1);
    s[0]=-1;
    for(int i=1;i‘a‘;
    fail[0]=1; len[1]=-1;
    for(int i=1;ii) 
        extend(i);
    for(int i=tot;i>1;--i) cnt[fail[i]]+=cnt[i];
    long long ans=0;
    for(int i=2;ilen[i]);
    printf("%lld",ans);
}

bzoj千题计划304：bzoj3676: [Apio2014]回文串

标签：fine span void 分享 using tps AC 回文串 geo

原文地址：https://www.cnblogs.com/TheRoadToTheGold/p/8687331.html

上一篇：restful API

下一篇：2、FreeRTOS任务相关API函数

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：bzoj千题计划304：bzoj3676: [Apio2014]回文串
文章链接：http://soscw.com/index.php/essay/76355.html

亲，登录后才可以留言！

bzoj千题计划304：bzoj3676: [Apio2014]回文串

评论

热门文章

推荐文章

最新文章

置顶文章