题意

对于字符串\(s\)的前\(i\)个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作\(num[i]\)。求\(\prod_{i=1}^L (num[i]+1)\; mod\; 1000000007\)。

分析

利用性质:

  •  \(Next[i]\)表示\(i-1\)为结尾的字符串的最长公共前后缀(不算本身)

可以得到,满足要求的数量就是不断的跳\(Next[x]\),但是要保证\(x\le \frac{y}{2}\),\(y\)为当前位置,\(x\)为前缀的结束位置。

但是直接这样跳复杂度不对,题目要求的复杂度是\(O(|S|)\)的。

我们考虑\(num[x]\)的计算方式,利用上面的分析可以知道,如果不考虑互相重叠的话,\(num[x]=num[Next[x]]+1\)。

显然\(num\)数组是递增的。那么考虑重叠的时候,显然\(num'[x]\)的值是嵌套的\(Next\)中,满足比\(\le\)一半的最后一个位置。

我们可以用类似于kmp匹配的方法。

如果当前位置\(x\)像后移动一位,那么他所对应的答案最多也是向后移动一位。

所以,如果当前指向的位置为\(k\),如果能匹配上则继续匹配下一位,当前的答案为\(num[k]\),如果匹配失败就往前跳;另一种情况是,当前的\(k>\frac{x}{2}\)(\(x\)是当前的位置)了,那么也是往前跳。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注