loj#P6806. String
String
题目描述
题目来自 2016 ACM/ICPC Asia Regional Qingdao Online
Alice 有一个只包含小写字母的字符串 ,现在她要对这个字符串进行 次操作,每次操作可以是在 末端新加入一个字符,或者选择 的某个子串 ,询问 的所有在 中至少出现两次的子串中,最长的子串长度是多少。如果 没有至少出现两次的子串,则结果应为 。
输入格式
第一行包含一个只包含小写字母的字符串 和正整数 ,分别表示 Alice 一开始持有的串和操作次数。
以下 行每行描述一个操作。为了正确读入所有数据,你需要维护一个变量 tmp
表示最后一次询问的结果,初始值为 。
如果读入的是 1 c
表示在字符串的末尾添加一个字符,这个字符的 ASCII 码应当等于 (c - 'a' + tmp) mod 26 + 'a'
。
如果读入的是 2 l r
表示选择 从第 (l - 1 + tmp) mod len + 1
位到 (r - 1 + tmp) mod len + 1
位(len
代表当前 的长度)的部分作为子串 ,询问 中最长的至少出现两次的子串长度,同时你应当把 tmp
更新为本次询问的结果。
字符串的初始长度和操作次数都不超过 。
输出格式
对每个询问操作,单独一行输出答案。
aabda 6
2 1 4
1 a
2 1 5
1 b
2 6 5
2 7 4
1
2
3
2
数据范围与提示
数据可能有点弱,如有问题请联系 @AntiLeaf