回文串[APIO2014](回文树)

2021-03-20 14:24

阅读：333

首先建出s的回文树，然后对于每一个回文子串，记录cnt为它出现的次数。

对于它fail树上的儿子，肯定都是它的子串（后缀），所以他出现了cnt次，它的后缀也会出现cnt次。

我们从更新的节点从后往前遍历，假设现在遍历到i，就使cnt[fail[i]]+=cnt[i]。然后更新ans=max(ans, cnt[i]*len[i])。

#include 
#include 
#include using namespace std;
const int N = 400000;
char s[N];
int lens;
long long ans;
namespace Plalindromic_Tree{
    struct node{
        int go[26];
        int fail, len;
    }pt[N];
    int lst = 0, tot = 0;
    int cnt[N];
    void build() {
        s[0] = -1;
        pt[++tot].len = -1;
        pt[0].fail = pt[1].fail = 1;
    }
    void add(int c, int n) {
        int p = lst;
        while (s[n - pt[p].len - 1] != s[n]) p = pt[p].fail;
        if (!pt[p].go[c]) {
            int v = ++tot, k = pt[p].fail;
            pt[v].len = pt[p].len + 2;
            while (s[n - pt[k].len - 1] != s[n]) k = pt[k].fail;
            pt[v].fail = pt[k].go[c];
            pt[p].go[c] = v;
        }
        lst = pt[p].go[c];
        cnt[pt[p].go[c]]++;
    }
}using namespace Plalindromic_Tree;
int main() {
    scanf("%s", s + 1);
    lens = strlen(s + 1);
    build();
    for (int i = 1; i ) {
        add(s[i] - ‘a‘, i);
    }
    for (int i = tot; i; i--) {
        cnt[pt[i].fail] += cnt[i];
        ans = max(ans, 1ll * cnt[i] * pt[i].len);
    }
    cout  ans;
    return 0;
}

上一篇：Windows电脑常用快捷键

下一篇：[C#.net]Connection Timeout和Command Timeout

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：回文串[APIO2014](回文树)
文章链接：http://soscw.com/index.php/essay/66735.html

亲，登录后才可以留言！

回文串[APIO2014](回文树)

评论

热门文章

推荐文章

最新文章

置顶文章