首页 > 试题广场 >

回文(version 3)

[编程题]回文(version 3)
\hspace{15pt}给定一个长度为 n 且仅包含小写字母的字符串 s_1s_2\cdots s_n，给定 q 次询问的三元组 (l,r,x)，每次询问求区间 [l,r] 内有多少个长度为 x 的回文子序列。

【名词解释】
\hspace{15pt}回文串：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。
\hspace{15pt}子序列：从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串。

输入描述:
\hspace{15pt}第一行两个整数 n,q(1\leqq n ,q\leqq 2\times 10^5)，表示字符串的长度和询问次数。

\hspace{15pt}第二行一个长度为 n 且仅包含小写字母的字符串 s。

\hspace{15pt}接下来 q 行 ，每行三个整数 l,r,x(1\leqq l\leqq r\leqq n,1\leqq x\leqq 3)，表示询问区间和询问回文子序列的长度。


输出描述:
\hspace{15pt}对于每次询问新起一行输出一个整数，表示当前询问区间有多少个长度为 x 的回文子序列。
示例1

输入

6 3
abcabc
1 3 1
1 4 2
1 6 3

输出

3
1
6
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 4浏览

热门推荐

相关试题

回文(version 3)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号