好像是去年毛子发明的对付回文串的数据结构。
下午再次研究了一遍,发现总算看懂了。
贴一份模板。

template<int maxn = int(1e5), int sigma = 26>
class PalindromeTree
{
private:
    int n, p, tail;
    int S[maxn];
    int next[maxn][sigma], fail[maxn], len[maxn], cnt[maxn];
    inline int idx(char c){return c - 'a';}

public:
    int newnode(int l)
    {
        cnt[p] = 0;
        len[p] = l;
        return p++;
    }
    void init()
    {
        newnode(0), newnode(-1);
        S[n = 0] = -1;
        fail[0] = 1;
    }

    int get_fail(int x)
    {
        while(S[n - len[x] - 1] != S[n])
            x = fail[x];
        return x;
    }

    void add(char c)
    {
        int id = idx(c);
        S[++n] = id;
        int cur = get_fail(tail);
        if(!next[cur][id])
        {
            int node = newnode(len[cur] + 2);
            fail[node] = next[get_fail(fail[cur])][id];
            next[cur][id] = node;
        }
        tail = next[cur][id];
        cnt[tail]++;
    }

    void count()
    {
        for(int i = p - 1; i >= 0; i--)
            cnt[fail[i]] += cnt[i];
    }
};

标签: none

添加新评论