★ FEATURED ARTICLE 不重合前后缀子串计数时间限制2 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述本题转译自 [NOI2014] 动物园。给定一个长度为n nn的字符串s ss下标从1 11开始。我们定义数组a aa中的第i ii个元素a i a_iai为第i ii个前缀P i s [ 1.. i ] P_i s[1..i]Pis[1..i]中满足以下条件的非空子串的数量既是P i P_iPi的前缀也是P i P_iPi的后缀该前缀与该后缀不重叠即两部分在下标意义上没有公共字符。现在请你计算如下表达式由于答案可能很大请将答案对( 10 9 7 ) (10^9 7)(1097)取模后输出( ∏ i 1 n ( a i 1 ) ) m o d ( 10 9 7 ) \left(\prod_{i1}^{n} (a_i 1)\right) \bmod (10^9 7)(i1∏n(ai1))mod(1097)【名词解释】字符串的前缀从字符串的第一个字符开始向后连续取若干个字符得到的字符串。更具体地字符串s ss前i ii个字符构成的字符串被称为s ss的第i ii个前缀也记为s [ 1.. i ] s[1..i]s[1..i]。子串从原字符串中连续地选择一段字符可以全选、也可以不选得到的新字符串。字符串的后缀从字符串的最后一个字符开始向前连续取若干个字符得到的字符串。更具体地字符串s ss后i ii个字符构成的字符串被称为s ss的第i ii个后缀也记为s [ n − i 1.. n ] s[n - i 1..n]s[n−i1..n]。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≤ T ≤ 5 ) T\ (1 \le T \le 5)T(1≤T≤5)代表数据组数每组测试数据描述如下在一行上输入一个长度为n nn仅由小写英文字母组成的字符串s ( 1 ≤ n ≤ 10 6 ) s\ (1 \le n \le 10^6)s(1≤n≤106)。输出描述对于每一组测试数据新起一行输出一个整数表示所求表达式的值对( 10 9 7 ) (10^9 7)(1097)取模后的结果。示例示例 1输入3 aaaaa ab abcababc输出36 1 32说明对于第一组测试数据第三个前缀P 3 aaa P_3 \texttt{aaa}P3aaa的符合条件子串仅有a \texttt{a}a故a 3 1 a_3 1a31第四个前缀P 4 aaaa P_4 \texttt{aaaa}P4aaaa的符合条件子串有a \texttt{a}a、aa \texttt{aa}aa故a 4 2 a_4 2a42。数据范围1 ≤ T ≤ 5 1 \le T \le 51≤T≤51 ≤ n ≤ 10 6 1 \le n \le 10^61≤n≤106字符串仅由小写英文字母组成解题思路本题是字符串前后缀匹配 差分统计的经典问题核心是统计每个前缀P i P_iPi中“既是前缀又是后缀且前后缀不重叠”的非空子串数量a i a_iai最后计算∏ i 1 n ( a i 1 ) \prod_{i1}^{n}(a_i1)∏i1n(ai1)。由于n ≤ 10 6 n\le 10^6n≤106需要线性或近似线性的字符串算法。1. 问题等价转化对于前缀P i s [ 1.. i ] P_is[1..i]Pis[1..i]一个长度为k kk的 border 需要满足k i kiki即长度严格小于i iis [ 1.. k ] s [ i − k 1.. i ] s[1..k]s[i-k1..i]s[1..k]s[i−k1..i]不重叠即前缀部分与后缀部分没有公共字符要求2 k ≤ i 2k\le i2k≤i。等价地若某个后缀的起始位置为j jj从 0 开始编号且前缀长度k kk满足k ≤ z [ j ] , k ≤ j k\le z[j],\qquad k\le jk≤z[j],k≤j其中z [ j ] z[j]z[j]表示从位置j jj开始的后缀与整个字符串的最长公共前缀长度则长度k kk的前缀也是从j jj开始的后缀并且不重叠。此时对于前缀P j k P_{jk}Pjk长度k kk就是一个合法的 border。因此对于每个后缀起点j jj所有满足1 ≤ k ≤ min ( z [ j ] , j ) 1\le k\le \min(z[j],j)1≤k≤min(z[j],j)的长度k kk都会给前缀P j k P_{jk}Pjk贡献一个合法 border。也就是说前缀长度L j k LjkLjk会获得一次贡献其中L ∈ [ j 1 , j min ( z [ j ] , j ) ] . L\in [j1,\ j\min(z[j],j)].L∈[j1,jmin(z[j],j)].2. 利用 Z 函数求匹配长度使用Z 函数扩展 KMP预处理字符串z [ i ] z[i]z[i]表示s [ i . . n − 1 ] s[i..n-1]s[i..n−1]与s [ 0.. n − 1 ] s[0..n-1]s[0..n−1]的最长公共前缀长度计算 Z 数组时维护当前匹配区间[ l , r ] [l,r][l,r]利用已求出的z zz值加速整体复杂度为O ( n ) O(n)O(n)。得到每个后缀起点的z [ i ] z[i]z[i]后就可以确定它对哪些前缀长度有贡献。3. 差分数组统计每个前缀的 border 数量由于对每个后缀起点i ii贡献的前缀长度是连续区间[ i 1 , i min ( z [ i ] , i ) ] . [i1,\ i\min(z[i],i)].[i1,imin(z[i],i)].因此使用差分数组a[]在区间左端点i1处加 1在区间右端点后一位imin(z[i],i)1处减 1。遍历所有后缀起点后对差分数组求前缀和即可得到每个前缀长度L LL对应的合法 border 数量a L a_LaL。4. 计算最终答案得到所有a i a_iai后按题目要求计算ans ∏ i 1 n ( a i 1 ) ( m o d 10 9 7 ) . \text{ans}\prod_{i1}^{n}(a_i1)\pmod{10^97}.ansi1∏n(ai1)(mod1097).由于a i ≤ n a_i\le nai≤n乘积过程中使用long long并每次取模避免溢出。5. 复杂度分析时间复杂度Z 函数计算O ( n ) O(n)O(n)差分更新O ( n ) O(n)O(n)前缀和与乘积统计O ( n ) O(n)O(n)。每组数据总复杂度O ( n ) O(n)O(n)。所有测试数据长度总和不超过限制可高效通过。空间复杂度需要存储 Z 数组和差分数组O ( n ) O(n)O(n)字符串本身O ( n ) O(n)O(n)。空间满足 256M 限制。总结通过 Z 函数求出每个后缀与整个串的最长公共前缀长度利用“不重叠”条件将合法 border 长度限制为k ≤ min ( z [ i ] , i ) k\le \min(z[i],i)k≤min(z[i],i)。再用差分数组对每个后缀起点贡献的连续前缀长度区间进行统计即可在线性时间内得到所有a i a_iai。最后按公式累乘( a i 1 ) (a_i1)(ai1)并取模得到答案。该方法巧妙地把 border 计数转化为区间加法问题避免了逐前缀枚举效率极高。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1000010;constll INF1e18;constll M1e610;constll mod1e97;string s;ll z[N],a[N];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cinT;while(T--){cins;ll ns.size();memset(a,0,sizeof(a));memset(z,0,sizeof(z));for(ll i1,l0,r0;in;i){if(irz[i-l]r-i1){z[i]z[i-l];}else{z[i]max(0LL,r-i1);while(iz[i]ns[z[i]]s[iz[i]])z[i];}if(iz[i]-1r){li;riz[i]-1;}a[i1];a[imin(z[i],i)1]--;}ll res1;for(ll i1;in;i){a[i]a[i-1];resres*(a[i]1)%mod;}coutres\n;}return0;}
阅读完成 · 觉得有帮助？
