P10992 [蓝桥杯 2023 国 Python A] 最长同类子串 题解

· · 题解

字符串哈希好题。

首先考虑如何判定两个串是否为同类串。我们不关心具体字符，只关心相同字母出现的位置，所以对于每个字母，使用它与上一个同样字母之间的距离作为多项式哈希的权值，即：

\operatorname{hash}(s)=\sum_{i=1}^{n} d_i \cdot B^{\,n-i} \pmod M

其中

d_i= \begin{cases} i-j, & \text{if } \exists j<i,\ s_j=s_i,\\[4pt] 0, & \text{otherwise}. \end{cases}

答案具有单调性，考虑二分最大长度 k。检查时用滑动窗口维护 S 所有长度为 k 的子串的哈希值出现次数（哈希表），再遍历 T 中每个长度为 k 的子串并查询即可。

时间复杂度 O(n\log n)。

代码丑陋就不放了。