首页 > 试题广场 >

车辆安排

[编程题]车辆安排
  • 热度指数：419 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
目前小马智行已经获得了加州RoboTaxi服务的许可，意味着小马智行已经可以在加州向所有的公众提供服务。
于是在未来的某一天，小马智行在加州已经拥有了N辆自动驾驶车辆可以面向公众服务，这些车总共有26种颜色，颜色分别为小写字母a到z。现在已知在Pony的服务系统PonyPilot中，总共有M个乘客正在排队，其中每个乘客也有各自的车辆颜色偏好,颜色范围也是a到z。
现在运营小P突然有了一个奇怪的想法：小P想知道总共有多少个位置连续的子队列，能够满足现有的所有车辆可以在同一时刻把子队列中的乘客同时接上乘客喜爱的颜色的车。注意每个车辆只能接一个乘客，且车的颜色要恰好是乘客喜欢的颜色。


输入描述:
第一行输入两个数字N，M。N代表车辆数，M代表乘客人数。

第二行输入一个字符串A，长度为N，表示每辆车的颜色。

第三行输入一个字符串B，长度为M，表示当前排队的乘客分别喜欢的车的颜色。

其中，1<=N<=1000000, 1<=M<=1000000。


输出描述:
输出一个数，即总共满足要求的子队列数。
示例1

输入

4 6
pony
pponyy

输出

12

说明

满足的子队列分别为（[]内为子队列对应的下标区间）：

p, [0, 0]
p, [1, 1]
o, [2, 2]
po, [1, 2]
n, [3, 3]
on, [2, 3]
pon, [1, 3]
y, [4, 4]
ny, [3, 4]
ony, [2, 4]
pony, [1, 4]
y, [5, 5]
示例2

输入

2 2
ab
ba

输出

3

说明

满足的子队列分别为（[]内为子队列对应的下标区间）：

b, [0, 0]
ba, [0, 1]
a, [1, 1]
算法知识视频讲解
开通博客

暂无题解

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 数据库工程师 信息技术岗 测试开发工程师 2019 大数据开发工程师 小马智行 数据分析师 Java工程师
上传者：小小
难度：
6条回答 4702浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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