Hey 伙计！先帮你分析下你尝试的两个序列，再聊聊Post对应问题（PCP）除了暴力枚举之外的实用方法~

先明确你的PCP实例：三个有序对分别是

• 对1：(x₁=1101, y₁=1)
• 对2：(x₂=0110, y₂=11)
• 对3：(x₃=1, y₃=110)

PCP的核心目标是找到非空的对序列（比如选对1、对3、对2这样的组合），让这些对的x串拼接起来，和对应的y串拼接起来完全相等。

现在看你尝试的两个序列：

1. 序列 1101.1.1.0110
   这应该是选了对1、对3、对3、对2（对应x串依次是1101、1、1、0110）。我们算下拼接结果：

   • 上串（x串拼接）：1101 + 1 + 1 + 0110 = 1101110110（10位）
   • 下串（y串拼接）：1 + 110 + 110 + 11 = 111011011（9位）
     光长度就不一样，肯定不相等，这个序列不是解。

2. 序列 110.1.110.110
   这个写法有点模糊——你的实例里没有任何一个对的x串是110（只有对3的y串是110）。如果是想选对3重复多次，那x串拼接是1111，y串是110110110110，完全不匹配；如果是其他组合，目前也找不到对应的对能拼出这个x序列，所以这个尝试也不是有效的解。

PCP本身是不可判定问题——不存在能解决所有PCP实例的通用算法，但针对小规模实例，有不少实用技巧可以提高效率：

• 长度剪枝法
  每次尝试一个序列分支时，先算当前上串和下串的长度差。如果这个差值的绝对值，超过了剩余所有对能提供的最大“长度补偿”，直接放弃这个分支。比如当前上串比下串长5位，而剩下的对里，最多只能让下串比上串多3位（比如对3的y串比x串长2位），那无论怎么选后续的对，都拉不平长度差，直接剪枝就行。

• 前缀匹配剪枝
  每次拼接一对后，比较上串和下串的公共前缀，只保留能让公共前缀延长的分支。比如拼接完对1后，上串是1101，下串是1，公共前缀是1，剩下的上串部分是101，下串部分是空。后续选的对必须满足：拼接后新的上串和下串能继续匹配前缀——如果某个位置字符不匹配，直接丢弃这个分支。

• 图论建模法
  把“剩余串差”作为节点：比如上串比下串长k位，剩余部分是S[k:]，就记为一个节点；或者下串比上串长k位，剩余部分是T[k:]，也是一个节点。每个对对应一条边：比如当前节点是剩余串A（上串比下串长len(A)），选对i后，新的拼接结果是A+x_i和y_i，如果A+x_i的长度 ≥ len(y_i)，且前len(y_i)位和y_i完全一致，那新节点就是(A+x_i)[len(y_i):]；如果y_i更长，且前len(A+x_i)位和A+x_i一致，新节点就是y_i[len(A+x_i):]。如果能走到空串节点，就说明存在解。

• 方程约束缩小范围
  先通过长度差建立方程，缩小枚举的可能组合。比如你的实例里：

  • 对1的长度差：len(x₁)-len(y₁)=4-1=+3（上串比下串长3）
  • 对2的长度差：4-2=+2
  • 对3的长度差：1-3=-2（下串比上串长2）
    要让总长度差为0，设选对1 a次，对2 b次，对3 c次，可得：3a + 2b - 2c = 0 → 3a = 2(c - b)。这说明a必须是偶数（因为右边是2的倍数），比如a=2时，c - b=3，也就是c=b+3。这样你就不用瞎试所有组合，只需要枚举a为偶数的情况，大大缩小尝试范围。

顺便帮你验证了下，这个实例是存在解的，比如序列：对3 → 对1 → 对3 → 对3 → 对2 → 对3，你可以自己动手拼接计算下，就能看到x串和y串完全匹配啦~

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