如何遍历二进制字符串提取唯一子串并存入字典？

核心逻辑 #

遍历二进制字符串时，从当前起始位置开始，优先尝试最短的未出现过的子串，将其存入字典（键从1开始递增），随后跳到该子串的末尾继续处理，直到遍历完整个字符串：

• 初始字典为空，从字符串第1位开始；
• 对当前起始位置，先取长度为1的子串：
  • 若不在字典中，直接加入字典，起始位置后移1位；
  • 若已存在，则逐步增加子串长度，直到找到一个不在字典中的子串，加入后将起始位置移到该子串末尾。

示例演示 #

输入字符串："1010100"
处理步骤：

1. 起始位置0，取子串'1'，不在空字典中，加入后字典为{1: '1'}，起始位置移到1；
2. 起始位置1，取子串'0'，不在字典中，加入后字典为{1: '1', 2: '0'}，起始位置移到2；
3. 起始位置2，取子串'1'已存在，扩展为'10'，不在字典中，加入后字典为{1: '1', 2: '0', 3: '10'}，起始位置移到4；
4. 起始位置4，取子串'1'已存在，扩展为'10'仍存在，再扩展为'100'，不在字典中，加入后字典为{1: '1', 2: '0', 3: '10', 4: '100'}，起始位置移到7，遍历完成。
   最终划分：|1|0|10|100|

代码实现（Python） #

def extract_unique_substrings(bin_str):
    result_dict = {}
    current_pos = 0
    key = 1
    str_length = len(bin_str)
    
    while current_pos < str_length:
        sub_length = 1
        while True:
            end_pos = current_pos + sub_length
            if end_pos > str_length:
                break
            current_sub = bin_str[current_pos:end_pos]
            if current_sub not in result_dict.values():
                result_dict[key] = current_sub
                key += 1
                current_pos = end_pos
                break
            sub_length += 1
    return result_dict

# 测试示例
test_str = "1010100"
print(extract_unique_substrings(test_str))
# 输出: {1: '1', 2: '0', 3: '10', 4: '100'}

说明 #

• 用current_pos跟踪当前处理的起始位置，每次找到唯一子串后直接跳转到子串末尾，避免重复遍历；
• 内层循环负责逐步加长子串长度，确保每次取到的是当前起始位置下最短的唯一子串；
• 题目明确无需考虑"00"这类特殊输入，因此代码未额外处理极端边界。

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