Dotcpp  >  编程题库  >   蓝桥杯2019年第十届国赛真题-逃出生天
题目 2561:

蓝桥杯2019年第十届国赛真题-逃出生天

时间限制: 1s 内存限制: 128MB 提交: 23 解决: 1

题目描述

“终于逃出这该死的塔了”。

在塔的底部,你看到了一扇门,这是距你获得自由的最后一道屏障了。当然,打开这扇门是需要密码的,密码可抽象为一个只包含小写字母的字符串。你并不知道密码具体是多少,但通过某种方式得到了生成密码的模版串s,并且知道密码一定是模板串的一个子串。你会尝试若干次,每次将得到一个字符串 t 和一段区间 [l,r],你会从选出 t 的一个子串去和 sl...r 匹配,定义两个字符串的匹配度为两个字符串的最长公共后缀长度 (最大的 x 使得两个串的后 x位相同)。你准备随机选出 t 的一个子串和 s 的这段区间匹配,并想知道匹配度的期望是多少,为了防止浮点误差,只需求出所有方案的匹配度的和即可。有时,你会发现你求的模板串出现了一些问题,需要对其中的一位进行修改,这个修改将会应用到以后的尝试上。更形式化地说,你需要维护以下两个操作:

• 1 x c,表示将 sx (即 s 的第 x 个字符) 修改为字符 c,保证 c 是小写字母;

• 2 t l r,表示给出一个字符串 t,求 t 的所有子串和 sl...r 的匹配度之和,匹配度的定义见上。

你决定玩一玩这个无聊的游戏,毕竟闲着也是闲着。

输入格式

输入的第一行包含一个只包含小写字母的字符串 s,表示生成密码的模板。
第二行包含一个正整数 n,表示操作次数。
接下来 n 行,每行形如 1 x c 或者 2 t l r,意义如题目所述。

输出格式

对于每组询问,输出一个整数,表示 t 的所有子串和 sl...r 的匹配度之和。

样例输入

bcca
4
2 acba 1 2
2 cab 1 4
1 2 b
2 bca 2 4

样例输出

2
3
6

提示


标签