有一个只包含小写字母n和t的字符串 s(1<=|s|<=1000000),其中如果有两个n相邻,那么它们可以合并成一个m,现在需要你去求这个字符串中,含有多少个 'mtm' 这样的子序列。输入一行字符串 s;输出这个字符串中所包含的 mtm 子序列的个数。
对于每一个 t 进行单独考虑,计算这个 t 的左侧和右侧分别可以合成出多少种不同的 m,这两个数的乘积就是对于这个 t 来说的 mtm 子序列的个数。因为只有相邻的 n 才可以合成 m,所以 t 将原来的字符串分成了一系列 n 的串。例如:nnntnnnntnntnnn 被分成了 nnn nnnn nn nnn没有段包含的 m 个数分别为 2312对 于 每 个 t 来 说 的 mtm 子 序 列 就 分 别 是 2*(3+1+2) 、(2+3)*(1+2)、(2+3+1)*2;所以结果为 12+15+12=39 因此输入:"nnntnnn" 输出:4
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。