找出所有 Runs 之后即可求出每一个位置作为三个串循环的结尾时以及作为两个串循环的开头时，串长的最小值，即可求出每个位置作为结尾时符合条件的串的左端点的最大值。通过预处理这个信息的前缀 $\max$ 即可做到 $\mathcal{O}(1)$ 回答询问。
时间复杂度为 $\mathcal{O}(N \log N + Q)$。
QOJ.ac
QOJ
Discussion #1345 for Problem #17423. Find "rururutata"
Type: Editorial
Status: Open
Posted by: Milmon
Posted at:
Last updated:
题解
Comments
No comments yet.