一. 题目

二. 思路

三. 代码

using LL=long long;
using PII=pair<int, int>;
const int N=1e5+10, S=131, MOD=1e9+7;

int n;
vector<int> sortedSon[N];
vector<char> dfsStr;//按题意得到的字符数组
PII seg[N];//映射点i对应的dfsStr区间

class SingleLinkedList
{
public:
    int h[N], e[N], ne[N], idx;
public:
    void init()
    {
        idx=0;
        fill(h, h+N, -1);
        fill(e, e+N, 0);
        fill(ne, ne+N, 0);
    }

    void add(int a, int b)
    {
        e[idx]=b, ne[idx]=h[a], h[a]=idx++;
    }
}sll;

class StrHash
{
public:
    LL head[N], tail[N], sys[N];
public:
    void makeHash(vector<char> str)
    {
        sys[0]=1, head[0]=tail[0]=0;
        for(int i=1, j=n;i<=n;++i, --j)
        {//head abc， tail cba
            sys[i]=getMod(sys[i-1]*S);//head[i]表示以1~i这段前高后低的哈希值
            head[i]=getMod(head[i-1]*S+str[i]);//高位~低位
            tail[i]=getMod(tail[i-1]*S+str[j]);//tail是把尾当作头，把头当做尾，低位~高位
            //tail[i]表示，n ~ n-i+1这段，前高后低的哈希值，这样可以共用同一个getHash函数
        }
    }

    LL getHash(LL has[], int l, int r)
    {
        // return getMod(hash[r]-hash[l-1]*sys[r-l+1]);
        return getMod(has[r]-has[l-1]*sys[r-l+1]);
    }

    LL getMod(LL x)
    {
        return (x%MOD+MOD)%MOD;
    }
}sh;

class Solution {
public:
    void init(string &s)//清空数组
    {
        n=s.size();
        sll.init();
        dfsStr.clear(), dfsStr.emplace_back('#');//映射到从下标1开始
        for(int i=0;i<n;++i)
            sortedSon[i].clear();
    }

    void buildTree(vector<int>& parent)//建树
    {
        for(int i=1;i<n;++i)//预处理有序儿子, 0为树根
            sortedSon[parent[i]].emplace_back(i);
        for(int i=0;i<n;++i) //从大到小对儿子排序，因为是头插法
            sort(sortedSon[i].begin(), sortedSon[i].end(), greater<int>());
        for(int i=0;i<n;++i)
            for(auto &son:sortedSon[i])//加边
                sll.add(i, son);
    }

    void dfs(int u, string &s)
    {
        seg[u].first=dfsStr.size();//当前起点就是，已经放置的dfsStr数量+1, 由于有个'#'所以为.size()
        for(int i=sll.h[u];~i;i=sll.ne[i])
        {
            int j=sll.e[i];
            dfs(j, s);
        }
        dfsStr.emplace_back(s[u]);//所有儿子遍历完了，加入当前自身的字符
        seg[u].second=dfsStr.size()-1;//正常是dfs.size(), 但是多个'#'
    }

    vector<bool> findAnswer(vector<int>& parent, string s) {
        init(s);
        buildTree(parent);
        dfs(0, s);//求出seg和dfsStr
        sh.makeHash(dfsStr);

        vector<bool> ans;
        for(int i=0;i<n;++i)
        {                                       //54321
            int l=seg[i].first, r=seg[i].second;//12345 n=5
            bool isH=(sh.getHash(sh.head, l, r)==
                      sh.getHash(sh.tail, n-r+1, n-l+1));
            ans.emplace_back(isH);
        }
        return ans;
    }
};