//求字符串s中最大回文的长度,要求字符串s不包含字符‘#’        int manacher(const string &s)        {            if (s.size() <= 1)                return s.size();                    //往s每个字符之间以及s的首尾都插入‘#’            string str(s.size() * 2 + 1, '#');            for (int i = 0, j = 1; i<s.size(); ++i, j += 2)                str[j] = s[i];                        int maxr = 2, id = 1, size = str.size();//maxr是当前最大回文的半径            vector<int> p(size, 1);            p[1] = 2;                    for (int i = 2; i <= size-3; ++i)            {                int maxright = p[id] + id - 1;                if (i>maxright)                {                    while (i - p[i] >= 0 && i + p[i]<size && str[i + p[i]] == str[i - p[i]])                        ++p[i];                }                else                {                    int idleft = id - p[id] + 1;                    int k = i - id, j = id - k, tmp = j - p[j] + 1;//i和j关于id对称                    if (tmp>idleft)                        p[i] = p[j];                    else if (tmp<idleft)                        p[i] = p[id] - k;                    else                    {                        p[i] = p[j];                        while (i - p[i] >= 0 && i + p[i]<size && str[i + p[i]] == str[i - p[i]])                            ++p[i];                    }                        }                if (p[i] + i>p[id] + id)                    id = i;                maxr = max(maxr, p[i]);            }                    return maxr - 1;                }