Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 6228 --3、自动驾驶(autopilot)
6228: 3、自动驾驶(autopilot)
警告!
题目
状态
题解
题目描述
作为人工智能的重要应用领域,自动驾驶有望重塑现有的交通模式。小可可团队正在研发一种自动驾驶算法模型,模型约定汽车在单位时间内行驶状态只有下列四种: 前进,用大写字母“F”表示。 后退,用大写字母“B”表示。 左转,用大写字母“L”表示。 右转,用大写字母“R”表示。 算法运行一段时间后,汽车的行驶过程可以描述为一条长度为n,且仅包含大写字母“F”、“B”、“L”和“R”的字符串S。小可可关注的是S 串中由k 个连续字符组成的子串,其中有些子串在S 串中反复出现。现在,小可可请你统计出所有重复出现的长度为k 的子串数量,这对预测汽车行驶状态的研究有重要意义。
输入
共2 行,第一行输入2 个正整数n, k,分别表示字符串S 的长度和子串的长度。第二行:长度为n,由大写字母“F”、“B”、“L”和“R”组成的字符串S。
输出
共1 行一个整数,表示表示字符串S 中出现次数大于1 的长度为k 的子串数量。
样例输入输出
输入#1
复制
30 7 FFFFFLLFFFFFLLLLFFFFFBBBFFBBRR
输出#1
复制
2
输入#2
复制
28 10 FFFFFFFFFFFFFFFFFFFFFBBBFFBB
输出#2
复制
1
提示
【样例1解释】:字符串S 中只有子串(长度为7)“FFFFFLL FFFFFLL ”和“LLFFFFF LLFFFFF ”出现了两次。 【样例2解释】:字符串S 中只有子串(长度为10 )“FFFFFFFFFF ”出现了12 次。 【数据范围:】 对于所有数据,50 ≤ n ≤ 10^6 ,2 ≤ k ≤ 10 。 测试点编号|n ≤ --|-- 1~4 |100 5~7 |1000 8~13 |10^5 14~20 |10^6
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及-
标签
字符串
点击显示
if ($pr_flag) { ?>
递交数
2
已通过
2
} ;?>
通过率
100%
时间限制
1 秒
内存限制
512 MB
来源
2023合肥
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和