首页 > 试题广场 >

可匹配子段计数

[编程题]可匹配子段计数
  • 热度指数：89 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定整数数组 a（长度 n）与数组 b（长度 m，m\leqq n）。设一个长度为 m 的数组 c 被称为 可匹配的，当且仅当将 c 的元素重新排列后，与数组 b 在对应位置上至少有 k 个元素相等。
\hspace{15pt}对于 a 中的每一个长度恰为 m 的连续子段，都可视为一个候选数组 c。求满足条件的子段数量。

【形式化解释】
\hspace{15pt}若子段 a_{l..l+m-1} 经重排可与 b 至少 k 个位置相等，则称该子段为"可匹配的"。等价地，设 cnt_x(S) 为元素 x 在序列 S 中出现次数，则子段 c 的"匹配度"为 \operatorname{match}(c)=\sum_{x} \min\bigl(cnt_x(c),\ cnt_x(b)\bigr)，若 \operatorname{match}(c)\geqq k 则符合要求。

输入描述:
\hspace{15pt}第一行输入整数 t\left(1\leqq t\leqq 10^{4}\right)——测试用例组数。 
\hspace{15pt}每个测试用例： 
{\hspace{23pt}}_\texttt{•}\,一行三个整数 n,m,k\left(1\leqq k\leqq m\leqq n\leqq 2\times10^{5}\right)； 
{\hspace{23pt}}_\texttt{•}\,一行 n 个整数 a_1\dots a_n\ \left(1\leqq a_i\leqq10^{6}\right)； 
{\hspace{23pt}}_\texttt{•}\,一行 m 个整数 b_1\dots b_m\ \left(1\leqq b_i\leqq10^{6}\right)。 
输入保证所有测试用例的 n 之和、m 之和均不超过 2\times10^{5}。


输出描述:
\hspace{15pt}对每个测试用例输出一行整数，表示满足条件的子段数量。
示例1

输入

1
4 1 1
4 1 5 6
6

输出

1
算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-08-12 16:38:09
题目链接 可匹配子段计数 题目描述 给定一个长度为 的整数数组 和一个长度为 的整数数组 （），以及一个整数 。 一个长度为 的数组被称为可匹配的，当且仅当该数组的元素重排后，能与数组 在对应位置上至少有 个元素相等。 我们需要对数组 中所有长度为 的连续子段进行判断，统计其中有多少 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

双指针
难度：
1条回答 25浏览

热门推荐

相关试题

可匹配子段计数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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