loj#P6806. String

String

题目描述

题目来自 2016 ACM/ICPC Asia Regional Qingdao Online

Alice 有一个只包含小写字母的字符串 SS,现在她要对这个字符串进行 mm 次操作,每次操作可以是在 SS 末端新加入一个字符,或者选择 SS 的某个子串 TT,询问 TT 的所有在 TT 中至少出现两次的子串中,最长的子串长度是多少。如果 TT 没有至少出现两次的子串,则结果应为 00

输入格式

第一行包含一个只包含小写字母的字符串 SS 和正整数 mm,分别表示 Alice 一开始持有的串和操作次数。

以下 mm 行每行描述一个操作。为了正确读入所有数据,你需要维护一个变量 tmp 表示最后一次询问的结果,初始值为 00

如果读入的是 1 c 表示在字符串的末尾添加一个字符,这个字符的 ASCII 码应当等于 (c - 'a' + tmp) mod 26 + 'a'

如果读入的是 2 l r 表示选择 SS 从第 (l - 1 + tmp) mod len + 1 位到 (r - 1 + tmp) mod len + 1 位(len 代表当前 SS 的长度)的部分作为子串 TT,询问 TT 中最长的至少出现两次的子串长度,同时你应当把 tmp 更新为本次询问的结果。

字符串的初始长度和操作次数都不超过 5×1045 \times 10 ^4

输出格式

对每个询问操作,单独一行输出答案。

aabda 6
2 1 4
1 a
2 1 5
1 b
2 6 5
2 7 4
1
2
3
2

数据范围与提示

数据可能有点弱,如有问题请联系 @AntiLeaf