Python中逐字符比较长度不同的子集字符串，获取失配字符与插入位置索引

核心比对逻辑 #

基于题目给出的短串为长串保序匹配子序列的约束（即短串的字符顺序和长串中的对应匹配字符顺序完全一致，不存在乱序），采用双指针逐位对齐遍历即可定位目标信息，流程如下：

• 初始化两个独立指针，分别从长串、短串的起始索引（位置0）开始遍历
• 每轮比对两个指针当前指向的字符：
  • 若字符完全相等：两个指针同时向后移动1位，记录当前匹配成功的长串位置为插入锚点
  • 若字符不相等：判定长串当前位置的字符是短串的缺失字符，仅移动长串指针，同时记录该缺失字符
• 当短串指针遍历到字符串末尾时，停止比对

流程验证（对应示例） #

以示例值str1='usay'（长串）、str2='usy'（短串）为例走完全流程：

1. 初始指针位置：长串指针指向0（字符u），短串指针指向0（字符u）——字符匹配，双指针右移到长串1、短串1
2. 当前长串位置1是字符s，短串位置1是字符s——字符匹配，记录锚点位置为1，双指针右移到长串2、短串2
3. 当前长串位置2是字符a，短串位置2是字符y——不匹配，记录缺失字符为a，仅将长串指针右移到3
4. 当前长串位置3是字符y，短串位置2是字符y——字符匹配，双指针右移到长串4、短串3
5. 短串指针走到末尾，遍历停止，最终得到锚点索引1（对应字符s），缺失字符为a，直接在s的位置后插入a即可完成匹配

可复用实现代码 #

def get_insert_info(long_str: str, short_str: str):
    p_long = 0
    p_short = 0
    missing_char_list = []
    last_match_long_idx = -1
    # 逐位匹配直到短串遍历完成
    while p_short < len(short_str) and p_long < len(long_str):
        if long_str[p_long] == short_str[p_short]:
            last_match_long_idx = p_long
            p_long += 1
            p_short += 1
        else:
            missing_char_list.append(long_str[p_long])
            p_long += 1
    # 处理长串尾部未匹配的剩余字符
    while p_long < len(long_str):
        missing_char_list.append(long_str[p_long])
        p_long += 1
    return {
        "insert_anchor_index": last_match_long_idx,
        "anchor_char": long_str[last_match_long_idx] if last_match_long_idx != -1 else None,
        "missing_chars": missing_char_list
    }

# 测试调用
test_long = "usay"
test_short = "usy"
res = get_insert_info(test_long, test_short)
# 输出结果: {'insert_anchor_index': 1, 'anchor_char': 's', 'missing_chars': ['a']}

方案特性 #

• 时间复杂度为O(max(长串长度, 短串长度))，无额外哈希、排序开销，适配大长度字符串的处理场景
• 支持连续多缺失字符的识别，比如长串为usxxay、短串为usy时，可自动收集所有缺失字符x、a，锚点位置不受连续缺失字符的影响
• 严格匹配题目约束场景，不额外兼容字符乱序、重复字符错位匹配的非目标情况

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