受限C++环境下基于特定参考点的字符位置查找问题

问题回顾 #

给定输入1为包含无限字符的句子（示例：Life is Beautiful），输入2为需查找位置的字符集合（示例：fee）。需将输入1经去重、排序后的中间字符作为零点参考点，计算输入2中每个字符的对应位置。重要限制：不得使用C++的string、array、vector等可存储无限字符的库。

核心思路 #

因为不能用动态容器，我们可以利用ASCII字符的有限范围（0-127，覆盖所有标准ASCII字符）来实现需求，步骤如下：

• 去重处理：用一个固定大小的布尔数组标记输入1中出现过的字符，完成去重。
• 收集并排序：把所有出现过的字符收集到固定数组中，再进行排序。
• 确定零点：以排序后字符数组的中间索引位置作为零点（比如数组长度为n，零点索引为n/2，整数除法），该位置的字符对应偏移量0。
• 计算位置：遍历输入2的每个字符，找到它在排序数组中的索引，用索引 - 零点索引得到相对位置；若字符未在输入1中出现，返回特殊值（比如-1）。

代码实现 #

#include <iostream>
#include <algorithm>

int main() {
    // 1. 标记输入1中出现的字符（去重）
    bool char_seen[128] = {false};
    char input_char;
    
    // 读取输入1，直到换行结束（可根据实际需求调整终止条件）
    while (std::cin.get(input_char)) {
        if (input_char == '\n') break;
        // 用unsigned char避免负数索引
        char_seen[(unsigned char)input_char] = true;
    }

    // 2. 收集去重后的字符并排序
    char unique_chars[128];
    int char_count = 0;
    for (int i = 0; i < 128; ++i) {
        if (char_seen[i]) {
            unique_chars[char_count++] = static_cast<char>(i);
        }
    }
    // 对固定数组排序，不依赖动态容器
    std::sort(unique_chars, unique_chars + char_count);

    // 3. 确定零点索引
    int zero_index = char_count / 2;
    // 可选：打印零点参考字符，方便验证
    // std::cout << "零点参考字符：" << unique_chars[zero_index] << std::endl;

    // 4. 处理输入2，计算每个字符的相对位置
    std::cout << "结果：";
    while (std::cin.get(input_char)) {
        if (input_char == '\n') break;
        
        // 字符未在输入1中出现的情况
        if (!char_seen[(unsigned char)input_char]) {
            std::cout << "-1, ";
            continue;
        }

        // 查找字符在排序数组中的索引
        int char_pos = 0;
        while (char_pos < char_count && unique_chars[char_pos] != input_char) {
            char_pos++;
        }

        // 计算相对零点的位置
        int offset = char_pos - zero_index;
        std::cout << offset << ", ";
    }
    std::cout << "\b\b " << std::endl; // 去掉最后多余的逗号和空格

    return 0;
}

关键细节说明 #

• 去重逻辑：char_seen[128]数组直接对应ASCII码值，标记字符是否出现，时间复杂度O(1)，完全避开动态容器。
• 排序处理：用标准库的std::sort对固定数组排序，只需要数组的首尾指针，不依赖动态容器的特性。
• 输入处理：用std::cin.get()逐个读取字符，支持处理任意长度的输入（直到终止条件），符合“无限字符句子”的需求。
• 边界处理：对未出现的字符返回-1，同时用unsigned char转换避免ASCII扩展字符导致的负数索引问题。

示例测试 #

假设输入1为Life is Beautiful，去重排序后的字符数组（按ASCII顺序）为：空格, B, L, a, b, e, f, i, l, s, t, u（共12个字符），零点索引为12/2=6，对应字符f。
输入2为see：

• s在排序数组中的索引是9，偏移量为9-6=3
• e的索引是5，偏移量为5-6=-1
• e同上，偏移量为-1
  最终输出为3, -1, -1（和示例的输出差异可能是零点定义的细微调整，比如取(char_count-1)/2作为零点索引，可根据需求修改）。

内容的提问来源于stack exchange，提问作者Alex Ham