题意：

一个回文的价值为长度 * 出现次数，问一个串中的子串的最大回文价值

思路：

回文树模板题，跑PAM，然后计算所有节点出现次数。

参考：

代码：

#include<map>

#include<set>

#include<cmath>

#include<cstdio>

#include<stack>

#include<ctime>

#include<vector>

#include<queue>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn = 300000 + 5;

const int INF = 0x3f3f3f3f;

const ll MOD = 1e9 + 7;

using namespace std;

struct PAM{

    int nex[maxn][26];  //指向的一个字符的节点

    int fail[maxn]; //失配节点

    int len[maxn];  //当前节点回文长度

    int str[maxn];  //当前添加的字符串

    int cnt[maxn];  //节点出现次数

    int last;

    int tot;    //PAM中节点数

    int N;  //添加的串的个数

    int newnode(int L){ //新建节点

        for(int i = 0; i < 26; i++) nex[tot][i] = 0;

        len[tot] = L;

        cnt[tot] = 0;

        return tot++;

    }

    void init(){

        tot = 0;

        newnode(0);

        newnode(-1);

        last = 0;

        N = 0;

        str[0] = -1;

        fail[0] = 1;

    }

    int getfail(int x){ //失配

        while(str[N - len[x] - 1] != str[N]) x = fail[x];

        return x;

    }

    void add(char ss){

        int c = ss - 'a';

        str[++N] = c;

        int cur = getfail(last);    //最长可扩增回文节点

        if(!nex[cur][c]){

            int now = newnode(len[cur] + 2);

            fail[now] = nex[getfail(fail[cur])][c];

            //cur后缀(除自己)的最长的能让now失配的后缀

            nex[cur][c] = now;

        }

        last = nex[cur][c];

        cnt[last]++;

    }

    void count(){

        for(int i = tot - 1; i >= 0; i--)   //父节点加上子节点出现的次数

            cnt[fail[i]] += cnt[i];

    }

}pa;

char s[maxn];

int main(){

    scanf("%s", s);

    pa.init();

    int len = strlen(s);

    for(int i = 0; i < len; i++){

        pa.add(s[i]);

    }

    pa.count();

    ll ans = 0;

    for(int i = 0; i < pa.tot; i++){

        ans = max(ans, ll(pa.len[i]) * ll(pa.cnt[i]));

    }

    printf("%lld\n", ans);

    return 0;

}

巴特西

BZOJ 3676 回文串（回文树）题解

题意：

思路：

参考：

代码：

最新文章

热门文章