hdu6599 I Love Palindrome String

深藏阁楼爱情的钟 2023-06-03 02:53 12阅读 0赞

由样例可知，题目中求的回文串数量，其实是本质不同的回文串数量，这个可以直接用回文树来做。

考虑前半段是回文串这个限制，这个东西回文树不好做，可以再套一个马拉车，然后记录一下插入到回文树的节点中最后一个字符的位置，使用马拉车快速判断这一段的前半段是不是回文串

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <queue>
    #include <vector>
    #define fo(i, l, r) for (int i = l; i <= r; i++)
    #define fd(i, l, r) for (int i = r; i >= l; i--)
    #define mem(x) memset(x, 0, sizeof(x))
    #define ll long long
    using namespace std;
    const int maxn = 300050;
    ll read()
    {
        ll x = 0, f = 1;
        char ch = getchar();
        while (!(ch >= '0' && ch <= '9'))
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        };
        while (ch >= '0' && ch <= '9')
        {
            x = x * 10 + (ch - '0');
            ch = getchar();
        };
        return x * f;
    }
    
    char Ma[maxn * 2];
    int Mp[maxn * 2];
    void Manacher(char s[], int len)
    {
        int l = 0;
        Ma[l++] = '$';
        Ma[l++] = '#';
        for (int i = 0; i < len; i++)
        {
            Ma[l++] = s[i];
            Ma[l++] = '#';
        }
        Ma[l] = 0;
        int mx = 0, id = 0;
        for (int i = 0; i < l; i++)
        {
            Mp[i] = mx > i ? min(Mp[2 * id-i], mx-i) : 1;
            while (Ma[i + Mp[i]] == Ma[i-Mp[i]])
                Mp[i]++;
            if (i + Mp[i] > mx)
            {
                mx = i + Mp[i];
                id = i;
            }
        }
    }
    
    const int N = 300010, S = 26;
    int all, son[N][S], fail[N], cnt[N], len[N], text[N], pos[N], last, tot;
    int newnode(int l)
    {
        for (int i = 0; i < S; i++)
            son[tot][i] = 0;
        cnt[tot] = 0, len[tot] = l;
        return tot++;
    }
    void init()
    {
        last = tot = all = 0;
        newnode(0), newnode(-1);
        text[0] = -1, fail[0] = 1;
    }
    int getfail(int x)
    {
        while (text[all - len[x] - 1] != text[all])
            x = fail[x];
        return x;
    }
    void add(int w,int p)
    {
        text[++all] = w;
        int x = getfail(last);
        if (!son[x][w])
        {
            int y = newnode(len[x] + 2);
            fail[y] = son[getfail(fail[x])][w];
            son[x][w] = y;
            pos[y] = p;
        }
        cnt[last = son[x][w]]++;
    }
    void count()
    {
        for (int i = tot - 1; ~i; i--)
            cnt[fail[i]] += cnt[i];
    }
    char s[maxn];
    int slen, s2[maxn];
    ll ans[maxn];
    int flag;
    inline bool check(int l,int r){
        int len = r-l+1;
        if(len==1)return true;
        r = (l+r)>>1;
        len = r-l+1;
        if(len&1){
            int t = l + (len>>1);
            t *= 2;
            return Mp[t]-1 >= len;
        }else{
            int t = l + (len >> 1);
            t = t*2-1;
            return Mp[t]-1 >= len;
        }
    }
    void dfs(int u, int d)
    {
        fo(i, 0, 25)
        {
            if (son[u][i])
            {
                s2[d + 1] = i;
                dfs(son[u][i], d + 1);
            }
        }
        if (d)
        {
            int lenu = d + d - flag;
            int rp = pos[u];
            int lp = pos[u]-lenu+1;
            if(check(lp,rp))ans[d + d - flag] += cnt[u];
        }
    }
    int main()
    {
        int tt = 0;
        int T;
        while (scanf("%s", s + 1) != EOF)
        {
            init();
            memset(ans, 0, sizeof(ans));
            slen = strlen(s + 1);
            fo(i, 1, slen)
            {
                add(s[i] - 'a',i);
            }
            count();
            Manacher(s+1,slen);
            flag = 0;
            dfs(0, 0);
            flag = 1;
            dfs(1, 0);
            printf("%lld", ans[1]);
            fo(i, 2, slen)
            {
                printf(" %lld", ans[i]);
            }
            putchar('\n');
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hyfer/p/11575134.html