开发者社区> 问答> 正文

遇到一个2n合体问题,求解答

有一个只包含小写字母n和t的字符串 s(1<=|s|<=1000000),其中如果有两个n相邻,那么它们可以合并成一个m,现在需要你去求这个字符串中,含有多少个 'mtm' 这样的子序列。输入一行字符串 s;输出这个字符串中所包含的 mtm 子序列的个数。

展开
收起
游客4skzfvnrxrzbi 2021-12-23 17:08:42 355 0
1 条回答
写回答
取消 提交回答
  • 对于每一个 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

    2021-12-23 18:55:43
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
属兔的处子——Clojure太灵活,臣妾驾驭不住啊 立即下载
YunOS让万物跟人自由口语交互 立即下载
鱼和熊掌可得兼-双内核特性解读 立即下载