贝壳找房 · 字符串 · 算法编程题
贝壳找房 字符串 t ≤ 1e4 时限 1 秒 / 64 MB

题目描述

牛牛的吉他老师牛妹告诉他，吉他初学者需要熟练弹奏三个旋律： 63231323, 53231323, 43231323 ，即：吉他从下到上一共 6 根弦，依次编号为 1 ~ 6 ，然后右手分别用相应的手指按照上述顺序拨动对应的弦。
牛牛为了测试牛妹老师的专业性，故特意出了一个问题刁难她。
首先，牛牛给三个基本旋律编个号， 1 号对应 63231323 ， 2 号对应 53231323 ， 3 号对应 43231323 。
接着，给出一个仅包含数字 1, 2, 3 的序列，再将这个序列转化成对应的旋律，例如：序列为 13 ，那么对应的旋律为 6323132343231323 。
然后，牛牛即兴弹奏一曲，他希望牛妹在听完之后能够回答出，这段即兴弹奏中一共出现了多少次事先定义的旋律。

输入输出

输入描述
本题为多组测试数据，第一行输入一个正整数 T( 1≤ T≤ 10) ，代表测试数据组数。
对于每组测试数据，第一行输入一个仅包含 1, 2, 3 的字符串 t( t≤ 10000) ，代表牛牛事先指定的旋律。
第二行输入一个仅包含 1 ~ 6 的字符串 s( s≤ 1000000) ，代表牛牛弹奏的旋律。
输出描述
对于每段演奏，一行输出一个整数，代表这段演奏一共包含了多少次事先指定的旋律。

样例共 1 组

样例 1
输入
1
22
532313235323132353231323
输出
2

算法解析依据充分

考点：字符串

数据规模 t ≤ 1e4 ｜ 限制 1 秒 / 64MB ｜ 标准输入输出

题目画像

  • 数据规模：t ≤ 1e4，T ≤ 10
  • 元素值域：s ≤ 1e6（注意整数类型选择，避免溢出）
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：字符串

本题切入点

先把 1/2/3 序列展开成完整旋律串，再在弹奏串中统计目标串的出现次数，可用 KMP 处理长串。

按字符逐个处理，或利用字符串的前后缀性质加速匹配。

思路框架（字符串 通法 · 非本题专属）

  1. 明确操作对象是字符还是子串、是否需要保持原顺序。
  2. 子串问题常用双指针 / 滑动窗口；回文问题可用中心扩展或哈希。
  3. 多模式匹配考虑 Trie 或 KMP；只需计数则用哈希表统计字符频次。
  4. 注意字符集大小写敏感性与输入是否带引号。

实现要点：Python 切片 s[l:r+1] 取子串；注意字符串不可变，频繁拼接改用 list。

复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(n)

该范式的通法易错点

  • 下标与切片边界差 1。
  • 忽略了大小写、空白字符的影响。

对照本题

  • 数据规模 t ≤ 1e4，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 元素值域最大到 1e6 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：1 / 22 / 532313235323132353231323
  • 输出：2

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：贝壳找房2023届校招移动端类试卷。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解