HDU第二场 ILovePalindromeString

这个题算是一个比较裸的回文树了，至少我当时第一想法这是个模板题。

首先我们需要知道一个十分显然的结论，对于一个长度为的回文串，最多只有不超过种本质不同的回文子串，知道了这一点我们再来考虑怎么处理这个题。

对于一个回文树，我们可以得到的信息有这个节点所代表的回文子串在整个字符串中出现的次数，这个恰好是该题解题的关键。考虑回文树的构造过程，仔细观察可以发现当我们添加一个字符时，只有当产生本质不同的回文子串时，才会产生新的节点，否则我们只需要在对该回文节点的加一就行了，因此，我们可以在构造回文串时顺带把该回文子串的右端点加入，这样我们在统计答案时，就能得到该回文串在原串中的左右端点。然后我们只需要对串正反进行一次就能判断是否满足到是否满足是回文串这个条件。这样我们就能在时间内解决这个题。

//author Forsaken
#define Hello the_cruel_world!
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<utility>
#include<cmath>
#include<climits>
#include<deque>
#include<functional>
#include<numeric>
#define max(x,y) ((x) > (y) ? (x) : (y))
#define min(x,y) ((x) < (y) ? (x) : (y))
#define lowbit(x) ((x) & (-(x)))
#define FRIN freopen("std.in", "r", stdin)
#define FROUT freopen("std.out", "w", stdout)
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define outd(x) printf("%d\n", x)
#define outld(x) printf("%lld\n", x)
#define memset0(arr) memset(arr, 0, sizeof(arr))
#define il inline
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 3e5;
const int INF = 0x7fffffff;
const int mod = 1e9 + 7;
const ull base = 137;
const double eps = 1e-7;
const double Pi = acos(-1.0);
il int read_int() {
    char c;
    int ret = 0, sgn = 1;
    do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
    if (c == '-') sgn = -1; else ret = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    return sgn * ret;
}
il ll read_ll() {
    char c;
    ll ret = 0, sgn = 1;
    do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
    if (c == '-') sgn = -1; else ret = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    return sgn * ret;
}
il ll quick_pow(ll base, ll index, ll p) {
    ll res = 1;
    while (index) {
        if (index & 1)res = res * base % p;
        base = base * base % p;
        index >>= 1;
    }
    return res;
}
int res[maxn + 5];
ull coe[maxn + 5];
struct PAM {
    struct node {
        int child[26], cnt, fail, num, len, pos;
    }arr[maxn + 5];
    int last, n, tot;
    char s[maxn + 5];
    ull Hash[maxn + 5], rHash[maxn + 5];
    il void Get_hash() {
        for (int i = 1; i <= n; ++i)
            Hash[i] = Hash[i - 1] * base + s[i];
        reverse(s + 1, s + 1 + n);
        for (int i = 1; i <= n; ++i)
            rHash[i] = rHash[i - 1] * base + s[i];
    }
    il ull Get_hash_value(int l, int r) {
        return Hash[r] - Hash[l - 1] * coe[r - l + 1];
    }
    il ull Get_hash_value_re(int l, int r) {
        return rHash[r] - rHash[l - 1] * coe[r - l + 1];
    }
    il bool check(int l, int r) {
        ull hash1 = Get_hash_value(l, r);
        int len = r - l + 1;
        ull hash2 = Get_hash_value_re(n - r + 1, n - r + len);
        return hash1 == hash2;
    }
    il void clear() {
        for (int i = 0; i <= tot; ++i) {
            memset0(arr[i].child);
            arr[i].cnt = arr[i].fail = arr[i].len = arr[i].num = arr[i].pos = 0;
            rHash[i] = Hash[i] = 0;
        }
        last = n = 0;
        s[0] = '#';
        arr[0].fail = 1, arr[1].len = -1;
        tot = 1;
    }
    il int find_fail(int x) {
        while (s[n - arr[x].len - 1] != s[n])x = arr[x].fail;
        return x;
    }
    il void add(char c) {
        s[++n] = c;
        int cur = find_fail(last);
        if (!arr[cur].child[c - 'a']) {
            int now = ++tot;
            arr[now].len = arr[cur].len + 2;
            int p = find_fail(arr[cur].fail);
            arr[now].fail = arr[p].child[c - 'a'];
            arr[cur].child[c - 'a'] = now;
            arr[now].num = arr[arr[now].fail].num + 1;
            arr[now].pos = n;
        }
        last = arr[cur].child[c - 'a'];
        ++arr[last].cnt;
    }
    il void count() { for (int i = tot; i >= 0; --i)arr[arr[i].fail].cnt += arr[i].cnt; }
    il void solve() {
        for (int i = 2; i <= tot; ++i) {
            int len = arr[i].len;
            int pos = arr[i].pos;
            int mid = len / 2;
            if (len & 1)++mid;
            if(check(pos - len + 1, pos - len + mid))res[len] += arr[i].cnt;
        }
    }
}pam;
char S[maxn + 5];
int len;
int main()
{
    coe[0] = 1;
    for (int i = 1; i <= maxn; ++i)coe[i] = base * coe[i - 1];
    while (~scanf("%s", S + 1)) {
        len = strlen(S + 1);
        pam.clear();
        for (int i = 1; i <= len; ++i)pam.add(S[i]);
        for (int i = 1; i <= len; ++i)res[i] = 0;
        pam.count();
        pam.Get_hash();
        pam.solve();
        for (int i = 1; i <= len; ++i)printf("%d%c", res[i], " \n"[i == len]);
    }
    //system("pause");
    return 0;
}