首先看到这个 \(Q\) \(1e9\) 的范围和 \(R_i\) 下标的取模操作，便知道这个东西有循环节，因此稍微思考一下便可以求出循环节，但注意，字符串的首尾两个特殊位置是不在循环内的，需要特殊处理。
然后就处理掉了 \(Q\)，考虑线性求解。
容易发现，需要求的是不断在一个队列中加入字符串，并判断它的后缀重排后是否与另一个字符串 \(S\) 相等。暴力判断是平方的，但判断两个字符串是否相等，不难想到 \(hash\)。
考虑对每一个数随机映射一个值乱搞，因为这里是重排后相等，因此不能使用多项式 \(hash\)，即字符间没有相对顺序。
然后用双端队列维护一下就做完了。
标签：相等,hash,神树,删库,无论怎样,重排,字符串 From： https://www.cnblogs.com/louis660/p/16937353.html