华为 · 字符串 · 算法编程题
华为 字符串 n ≤ 5000 时限 1 秒 / 256 MB

题目描述

小红为日志系统定义了一个目标模式串 A 。对于任意字符串 B ，一次压缩操作可以选择两个相邻且相同的字符，并删除其中一个。如果经过若干次压缩后能够得到 A ，则称 B 是符合目标模式的字符串。
现在给定一个字符串 S ，请计算 S 中有多少个子串符合目标模式。两个内容相同但起止位置不同的子串需要分别计数。

输入输出

输入描述
第一行输入两个整数 n,m ，分别表示字符串 A 和 S 的长度。
第二行输入长度为 n 的字符串 A 。
第三行输入长度为 m 的字符串 S 。
保证 1 ≤ n,m ≤ 5000 ，两个字符串均只包含英文小写字母。
输出描述
输出一个整数，表示符合目标模式的子串数量。

样例共 1 组

样例 1 · 可以选择第一个连续字符段的任意非空后缀和第二个连续字符段的任意非空前缀，共得到 4 个符合要求的子串。
输入
2 4
ab
aabb
输出
4

算法解析依据一般

考点：字符串

数据规模 n ≤ 5000 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 5000，m ≤ 5000
  • 复杂度门槛：只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：字符串

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 n ≤ 5000，只允许 O(n log n) 及更优，朴素 O(n²) 会超时。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例解读

样例 1：输入 2 4 / ab / aabb → 输出 4

可以选择第一个连续字符段的任意非空后缀和第二个连续字符段的任意非空前缀，共得到 4 个符合要求的子串。

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

本题来源：2026年-华为-05月22号开发岗。

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