algorithm - 将新字符添加到回文。检查新字符串是否仍然是回文的有效或动态方法？

Question

假设我有一个回文s，为了好玩，我将继续在s 的末尾追加字符。但是一旦 s 不再是回文，我就想停下来。

现在我比较懒，所以不想每次在s后面追加一个新字符的时候，都重新扫描s来判断是不是回文。我想知道是否有更快的方法来公式化/检查新的 s 是否是回文，利用 s 已经是回文的事实。我觉得有一种方法可以利用这些信息，但我不能完全理解它。

---

我陷入了思考过程。到目前为止，我正在尝试将事情分解为案例。

回文s可以有两种形式:(|__M__|是s的子串部分和|__- M__| 是 |__M__| 的反转)

当长度为奇数时:

|__-M__|X|__M__|

当长度为偶数时:

|__-M__||__M__|

现在当我附加新字符 c 时是否有一种有效的方法来检查

|__-M__|X|__M__|c <---- 回文？

|__-M__||__M__|c <---- 回文？

Answer 1

从评论中形式化相同字符的猜想:

如果字符串 S 中具有 N 个字符的字符并非都相同，则必须有:

• 在索引 P1 处的字符 C1，后跟在 P1+1 处的不同 C2
• C1 位于镜像索引 N-1-P1，前面是 C2 位于 N-2-P1

将任何单个字符添加到 S 后，现在必须有:

• P1 处的字符C1，后跟P1+1 处的C2
• C1 在镜像索引处，现在是 N-P1，前面是 C2 在 N-1-P1

因此，N-1-P1 处的字符必须是C1(扩展前)和C2(扩展后)这是不可能的，因为我们说过它们是不同的。

因此，只有当原始字符串是一个字符的重复时，才有可能逐个字符地扩展它并保持其为回文。