题解 P3560 【[POI2013]LAN-Colorful Chain】

· · 题解

Solution

先求出每个数的 \text{Hash} 值，再将目标串的各个数的 \text{Hash} 值乘上各自出现次数，所得和即为目标串的 \text{Hash} 值。

记目标串长度为 len。

同理求出原串每个长度为 len 的字串的 \text{Hash} 值，并与目标串比较即可。利用双指针从左到右扫描，时间复杂度 O(n)。