C++实现序列匹配与分类处理

C++实现序列匹配与分类处理（详细教程）

问题背景

我们有两个整数序列：

• I 序列：存放原始数据。
• R 序列：存放需要匹配的关键值。

程序需要按照一定规则，从 I 中找出所有包含 R 元素的记录，并按照要求输出匹配信息。
在处理过程中，还需要对 R 序列进行排序和去重，以保证输出结果的正确性。

---

题目描述

输入格式：

1. 第一个整数为 R 的个数（记为 R_len）。
2. 接下来输入 R_len 个整数，构成 R 序列。
3. 然后输入一个整数 I_len，表示 I 序列的长度。
4. 接下来输入 I_len 个整数，构成 I 序列。

输出要求：

• 先输出匹配到的总结果数量。

• 然后依次输出：

  R值 匹配数量 匹配起始下标 匹配到的值...
  

• R 序列中每个值必须按升序去重后依次匹配。

• 若某个 R 值没有匹配到，则跳过。

---

样例输入与输出

输入：

5
6 3 6 3 0
15
123 456 786 453 46 7 5 3 665 453456 745 456 786 453 123

输出：

30 
3 6 
0 123 3 453 7 3 9 453456 13 453 14 123
6 7 
1 456 2 786 4 46 8 665 9 453456 11 456 12 756

（输出格式需按题目具体要求调整）

---

解题思路

Step 1：去重 + 排序 R

• 因为 R 序列中可能有重复值，所以先用 sort 排序，再用 unique 去重。
• 这样能保证匹配顺序和输出顺序都是从小到大。

Step 2：遍历 R，查找 I 中的匹配项

• 对于每个 R 值，在 I 序列中查找所有包含该 R 值的记录。
• 记录匹配的数量、在 I 中的起始下标、以及对应的匹配值。

Step 3：保存输出结果

• 用 vector 保存每个 R 的匹配结果。
• 最终计算总匹配数，按要求格式输出。

---

核心实现技巧

1. 排序与去重

sort(R.begin(), R.end());
R.erase(unique(R.begin(), R.end()), R.end());

这样可以确保 R 序列有序且不重复。

2. 记录匹配信息

• 使用结构体保存：

  struct MatchInfo {int Rvalue;       // R 值int count;        // 匹配数量vector<int> index; // 匹配位置vector<int> value; // 匹配的值
  };
  

3. 字符串/整数序列处理

• 由于题目是整数匹配，所以直接用 vector<int> 存储和遍历即可。

---

完整代码（详细注释）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct MatchInfo {int Rvalue;             // R值int count;              // 匹配数量vector<int> index;      // 匹配的起始下标vector<int> values;     // 匹配到的值
};int main() {int R_len;cin >> R_len; // 读取R的长度vector<int> R(R_len);for (int i = 0; i < R_len; i++) {cin >> R[i];}int I_len;cin >> I_len; // 读取I的长度vector<int> I(I_len);for (int i = 0; i < I_len; i++) {cin >> I[i];}// 对R进行排序和去重sort(R.begin(), R.end());R.erase(unique(R.begin(), R.end()), R.end());vector<MatchInfo> results;int totalCount = 0; // 总匹配数量// 遍历R，匹配Ifor (int r : R) {MatchInfo info;info.Rvalue = r;// 遍历I查找匹配for (int i = 0; i < I.size(); i++) {if (I[i] == r) {info.count++;info.index.push_back(i);info.values.push_back(I[i]);}}if (info.count > 0) { // 只保留有匹配的results.push_back(info);totalCount += info.count;}}// 输出总数量cout << totalCount;// 输出每个匹配结果for (auto &res : results) {cout << " " << res.Rvalue << " " << res.count;for (int idx : res.index) {cout << " " << idx;}for (int val : res.values) {cout << " " << val;}}cout << endl;return 0;
}

---

运行过程示例

假设输入：

5
0 3 6 3 3
15
4 5 6 10 4 5 6 9 6 7 8 6 4 6 0

执行步骤：

1. R = {0,3,6}（排序去重后）

2. 对每个 R 值匹配 I：

   • 0 → 找到 1 次
   • 3 → 找不到，跳过
   • 6 → 找到多次

3. 输出总数及详细匹配信息。

---

总结

• 本题核心是对 R 排序去重 + 遍历匹配 I。
• 输出格式要严格按题意要求。
• 可以用结构体保存中间结果，逻辑更清晰。