这个回溯操作咋实现啊，在网上也搜不到题解
限时1s，512MB

先贴我的解题思路
看到版本回溯我第一反应想到的就是可持久化数据结构，尝试把KMP产生的失配树可持久化，再在失配树上用倍增跳失配链，时间复杂度预计在O(n log ^ 2 n)
但是失配树的可持久化好难写，奋斗3h宣布放弃
发现题目并没有要求强制在线，可以考虑离线算法，具体如下：
对于操作1，将其与上一个版本的操作连边
对于操作2，将其与回溯的版本连边
除此之外将第0个版本与第1个版本连边
具体可以看下面这张图（以样例2为例）
把所有操作存起来，并对第0个版本进行dfs
dfs的时候可以得到子串
对于每个节点跑一下kmp
然后倍增跳失配链
问题应该就解决了
时间复杂度也是O(n ^ 2 log n)
浅浅估算一下会TLE
继续优化
观察到每次只会改动末尾的字符
而字符串前面的next值不会发生变动
可以不用在遍历到每个节点的时候
对整个字符串进行一边完整的KMP
我这里魔改了一下KMP
使其能够跳过字符串前面已经算过的next值的计算
直接去算最后一个字符的next
这样就可以把每次O(n)的运算压到均摊O(1)的时间内
最终时间复杂度为O(n log ^ 2 n)
空间复杂度懒得算
应该不会MLE
待会楼下贴代码
我这里两个样例都过了
你测一下试试