题解：瑞学堂 瑞瑞的字符统计

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】瑞学堂瑞瑞的字符统计【题目描述】瑞瑞得到了一串由小写字母组成的字符串S SS。他想统计这个字符串中所有回文子串中每个字母出现的总次数。回文串是指正读和反读都一样的字符串。单个字符被视为回文串。例如字符串aba的回文子串有a位置1b位置2a位置3aba整个串。其中字母a出现了4 44次字母b出现了2 22次。由于结果可能很大请输出每个字母出现次数对10 9 7 10^971097取模后的结果。请你帮助瑞瑞编写程序完成这个任务。【输入】输入一行一个字符串S SS仅由小写字母组成。【输出】输出26 2626个整数用空格分隔依次表示字母a到z在所有回文子串中出现的总次数对10 9 7 10^971097取模的结果。【输入样例】aba【输出样例】4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0【核心思想】问题分析给定字符串S SS求所有回文子串中每个字母出现的总次数对10 9 7 10^971097取模。这是一个Manacher 差分数组问题关键在于先用 Manacher 求出以每个位置为中心的回文半径再用差分技巧统计每个位置被多少个回文子串覆盖最后累加各字母的贡献。算法选择Manacher 算法求出以处理后字符串每个位置i ii为中心的最长回文半径d [ i ] d[i]d[i]差分数组二阶差分每个中心i ii的回文串对区间[ i − d [ i ] 1 , i d [ i ] − 1 ] [i-d[i]1, id[i]-1][i−d[i]1,id[i]−1]产生中间高两边低的三角形贡献用二阶差分将O ( n 2 ) O(n^2)O(n2)的区间覆盖优化为O ( n ) O(n)O(n)前缀和还原两次前缀和将差分数组还原为每个位置的实际覆盖次数关键步骤Manacher 预处理插入#统一奇偶回文计算d [ i ] d[i]d[i]二阶差分标记遍历每个中心i ii回文覆盖范围[ l , r ] [ i − d [ i ] 1 , i d [ i ] − 1 ] [l, r] [i-d[i]1, id[i]-1][l,r][i−d[i]1,id[i]−1]coeff[l] 1coeff[i1] - 2coeff[r2] 1两次前缀和还原覆盖次数cur coeff[i]一阶前缀和sum cur二阶前缀和cnt[i] sum统计字母贡献遍历处理后字符串对实际字符位置i ii非#非$ans[s[i]-a] cnt[i]去重修正每个回文子串被计算了两次奇数中心和偶数中心最终答案乘2 22的逆元( M O D 1 ) / 2 (MOD1)/2(MOD1)/2时间/空间复杂度时间复杂度O ( n ) O(n)O(n)ManacherO ( n ) O(n)O(n)差分标记和前缀和O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)处理后字符串、d dd数组、差分数组等Manacher 差分的核心思想回文覆盖的三角形分布以i ii为中心、半径为R RR的回文串位置j jj被覆盖当且仅当∣ j − i ∣ R |j-i| R∣j−i∣R覆盖次数随距离中心增加而递减形成三角形贡献二阶差分转常数操作三角形数列的二阶差分为常数通过1, -2, 1的标记将O ( n 2 ) O(n^2)O(n2)的逐点覆盖降为O ( 1 ) O(1)O(1)的区间标记对称性去重插入#后每个实际回文子串既对应某个原字符中心奇数长度也对应某个#中心偶数长度总贡献被计算两次需除以2 22模运算技巧用乘法逆元代替除法避免浮点精度问题适用于统计所有回文子串中各位置/字符贡献的问题核心在于将回文结构转化为区间覆盖再用差分优化统计【算法标签】#Manacher【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long避免中间计算溢出constintN100005*3,MOD1e97;// N为处理后字符串最大长度MOD为模数chara[N],s[N];// a存储原始字符串s存储处理后的字符串插入分隔符#intd[N];// d[i]为Manacher算法中以i为中心的最长回文半径intcoeff[N];// coeff用于差分数组记录每个位置作为回文中心次数的贡献intcnt[N],ans[26];// cnt[i]为位置i在所有回文子串中被覆盖的总次数ans[26]记录26个字母的出现次数// Manacher算法核心函数计算以每个位置为中心的最长回文半径voidget_d(char*s,intn){d[1]1;// 初始化以第一个字符为中心的回文半径为1// i遍历每个中心位置l和r维护当前最右回文串的左右边界for(inti2,l,r1;in;i){// 如果当前位置i在当前最右回文串[r]的范围内利用对称性初始化d[i]if(ir)d[i]min(d[r-il],r-i1);// 中心扩展尝试向两边扩展回文串while(s[i-d[i]]s[id[i]])d[i];// 更新最右回文串边界if(id[i]-1r)li-d[i]1,rid[i]-1;}}signedmain()// 使用signed main配合#define int long long{scanf(%s,a1);// 读入原始字符串intnstrlen(a1),k0;// n为原始字符串长度// 预处理在原始字符串的每两个字符之间以及首尾插入分隔符#s[0]$;// s[0]放哨兵字符$防止越界s[k]#;// 第一个字符为#for(inti1;in;i){s[k]a[i];// 放入原始字符s[k]#;// 在每个字符后插入#}nk;// 更新n为处理后字符串的长度get_d(s,n);// 执行Manacher算法// 第一步利用差分数组统计每个位置被多少个回文子串覆盖for(inti1;in;i){intRd[i];// R为以i为中心的回文半径if(R1)continue;// 半径为1表示只有自身单个#无实际字符贡献// 回文串在处理后字符串中的覆盖范围intli-R1;// 左边界intriR-1;// 右边界// 差分标记以i为中心的回文串对区间[l,r]内每个位置的贡献// 使用二阶差分技巧将三角形贡献转化为常数差分coeff[l](coeff[l]1)%MOD;// 左端点一阶差分1// 顶点右侧一阶差分从1变-1净变化-2coeff[i1](coeff[i1]-2MOD)%MOD;// 右端点外一阶差分从-1变0coeff[r2](coeff[r2]1)%MOD;}// 第二步通过两次前缀和还原每个位置被覆盖的次数intcur0,sum0;for(inti1;in;i){cur(curcoeff[i])%MOD;// 一阶前缀和当前一阶差分值sum(sumcur)%MOD;// 二阶前缀和当前位置被覆盖的总次数cnt[i]sum;// 记录位置i被覆盖的次数}// 第三步统计每个实际字母的出现次数for(inti1;in;i){// 只统计实际字符位置非#且非$的位置即原始字符串的字符位置if(s[i]!#s[i]!$){ans[s[i]-a](ans[s[i]-a]cnt[i])%MOD;// 累加该位置被覆盖的次数}}// 第四步输出结果// 每个实际回文子串在Manacher中被计算了两次奇数中心和偶数中心各一次所以答案要除以2intINV2(MOD1LL)/2;// 2在模MOD下的逆元MOD为质数且MOD为奇数(MOD1)/2即为2的逆元for(inti0;i26;i){ans[i]ans[i]*INV2%MOD;// 除以2乘逆元coutans[i] ;// 输出26个字母的结果}coutendl;return0;}【运行结果】aba 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0