← 返回比赛
已结束 GESP欢乐赛#43
← 上一题 下一题 →

A4800 | KMP算法

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

小明和小王是好朋友，他们正在一起学习字符串算法。今天，小明在学习 KMP 算法时遇到了一个难题：给定一个只包含大写字母的字符串$s$，问这个字符串中有多少个等于 $\text{"KMP"}$ 的子序列。小明想了很久，还是没有思路。

小王看到小明苦恼的样子，决定帮她简化问题。他告诉小明：数据保证字符串中的字符 M 只出现一次，这样问题应该会简单一些。 但即便如此，小明还是不知道如何解决这个问题。于是，小王决定请你来帮助小明，告诉她这个问题的答案。

$\large{数据范围}$
- $1 \leq |s| \leq 10^3$，其中 $|s|$是 $s$ 字符串的长度
- 字符串中只包含大写字母

输入格式

输入一个字符串占一行。

输出格式

输出一个数字占一行，表示答案

输入输出样例

输入 #1
KMPP
输出 #1
2
C++ 编辑器
输入
输出