B4392 [常州市赛 2025] 压缩

搬运自 。数据为民间数据。

小 Y 开发了一种名为“别重复”的新型数据压缩策略。“别重复”作用于字符串，若字符串中存在两个连续相同的子串，则会删除其中一个。例如，在字符串 $\tt alfalfaseeds$ 中，“别重复”可删除 $\tt seeds$ 中的一个 $\tt e$和 $\tt alfalfa$ 中的一个 $\tt lfa$，得到 $\tt alfaseds$。 “别重复”还能利用先前的删除效果，例如在 $\tt seventeenth\ baggage$ 中，先删除重复的 $\tt e$ 和 $\tt g$ 得到 $\tt sevententh\ bagage$，再删除重复的 $\tt ent$ 和 $\tt ag$，最终得到 $\tt seventh\ bage$。 当存在多个重复子串可删除时，最优的“别重复”会选择使最终字符串最短的方式。例如，在 $\tt ABBCDCABCDCD$ 中，优先删除开头的 $\tt B$ 再删除 $\tt ABCDC$ 可压缩为 $\tt ABCD$，而若先删除末尾的 $\tt CD$ 再删除 $\tt B$ 则最终只能得到 $\tt ABCDCABCD$。最优的“别重复”会选择先删除 $\tt B$ 再删除 $\tt ABCDC$ 的方式。 小 Y 要求为带通配符的二进制字符串（仅含 $\tt 0,1,\#$，$\tt\#$ 为通配符）实现最优的“别重复”算法。你需要在进行“别重复”压缩算法前为通配符进行赋值，值为 $\tt 0$ 或者 $\tt 1$，使得赋值之后的二进制字符串通过应用最优的“别重复”能得到最短的字符串。

一行一个带通配符的二进制字符串。

一行一个字符串表示应用最优的“别重复”能得到的最短字符串。数据保证应用最优的“别重复”能得到的最短字符串有且只有一种唯一情况。

本任务共有 $10$ 个数据。 对于全部数据：保证字符串长度不超过 $10^5$，数据保证应用最优的“别重复”能得到的最短字符串有且只有一种唯一情况。 |测试点编号|特殊性质| |:-:|:-:| |$1\sim2$|字符串长度不超过 $3$| |$3\sim4$|字符串中不包含 $\tt0$| |$5\sim8$|字符串中不包含 $\tt\#$| |$9\sim10$|无|