C++ 算法题：魔镜项链

题目描述 国王有一个魔镜，可以把任何接触镜面的东西变成原来的两倍——只是，因为是镜子嘛，增加的那部分是反的。比如一条项链，我们用'AB'来表示，不同的字母表示不同颜色的珍珠。如果把B端接触镜面的话，魔镜会把这条项链变为'ABBA'。如果再用一端接触的话，则会变成'ABBAABBA'（假定国王只用项链的某一端接触魔镜）。给定最终的项链，请编写程序输出国王没使用魔镜之前，最初的项链可能的最小长度。

输入描述 只有一个字符串，由大写英文字母组成（字母数<=100000），表示最终的项链。

输出描述 只有一个整数，表示国王没使用魔镜前，最初的项链可能的最小长度。

样例1 输入 'ABBAABBA' 输出 2

提示字母数<=100000 。

解题思路： 根据题目描述，国王每次使用魔镜都是从项链的一端接触魔镜，魔镜会把接触的部分变为原来的两倍，其中增加的部分是反的。

我们可以假设国王每次都是从项链的第一个字符或最后一个字符接触魔镜，然后根据题目描述的规则，逆向推导出国王没有使用魔镜之前的项链可能的最小长度。

具体步骤如下：

初始化变量length为项链的长度。
从项链的第一个字符开始，假设国王是从该字符接触魔镜，然后根据题目描述的规则，逆向推导出国王没有使用魔镜之前的项链可能的最小长度。
- 如果项链的最后一个字符和第一个字符相同，则将项链的最后一个字符删除，并将length减1。
- 如果项链的最后一个字符和第一个字符不相同，则项链的最后一个字符加到项链的前面，并将length加1。
- 重复上述步骤，直到项链的第一个字符和最后一个字符相同。此时，国王没有使用魔镜之前的项链可能的最小长度就是length的值。
重复步骤2，假设国王是从项链的最后一个字符开始接触魔镜，然后根据题目描述的规则，逆向推导出国王没有使用魔镜之前的项链可能的最小长度。
- 如果项链的最后一个字符和第一个字符相同，则将项链的第一个字符删除，并将length减1。
- 如果项链的最后一个字符和第一个字符不相同，则项链的第一个字符加到项链的末尾，并将length加1。
- 重复上述步骤，直到项链的第一个字符和最后一个字符相同。此时，国王没有使用魔镜之前的项链可能的最小长度就是length的值。
取步骤2和步骤3中得到的最小长度作为结果输出。

算法复杂度分析： 假设项链的长度为n，那么时间复杂度为O(n)。空间复杂度为O(1)。