为什么我们不能一次性可靠地测试回文

Question

我遇到了 "palindrome" 的概念。我试着通过阅读维基百科来理解

http://en.wikipedia.org/wiki/Palindrome#Computation_theory

该段落引起了我的注意

This means that it is impossible for a computer with a finite amount of memory to reliably test for palindromes on one pass.

我想测试给定的字符串是否 "palindrome" 是不是很简单？我快出码了。

public class Utils {
    private static final String SPECIAL_CHARACTERS_REGEX = "[\s!,]";

    private static String removeSpecialCharacters(String string) {
        return string.replaceAll(SPECIAL_CHARACTERS_REGEX, "");
    }

    public static boolean isPalindrome(String string) {
        String str = string.toLowerCase();
        str = removeSpecialCharacters(str);

        if (str.isEmpty()) {
            return false;
        }

        int head = 0;
        int tail = str.length() - 1;
        while (head < tail) {
            char h = str.charAt(head);
            char t = str.charAt(tail);

            if (h != t) {
                return false;
            }

            head++;
            tail--;
        }

        return true;
    }
}

乍一看好像没问题。

public static void main(String[] args) {
    String s = "";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // false

    s = "1";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true

    s = "12";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // false

    s = "123";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // false

    s = "taco cat";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true

    s = "A man, a plan, a canal, Panama!";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true

    s = "Amor, Roma";
    System.out.println(s + " -> " + Utils.isPalindrome(s)); // true
}

如果是这样，我可以知道为什么维基百科说不可能一次性测试回文吗？我是不是忽略了什么？

Answer 1

如果字符串的长度为 n，则您的代码使用 O(log(n)) 存储（索引 head 和 tail 需要 O(log(n)) 位）。因此，您的程序需要无限量的内存才能测试任意长的字符串。

复杂性分析在实际代码中的应用是困难的，通常在理论上是不可靠的：显然在Java head 和tail 中都是整数，每个都是 32 位长。但是复杂性分析处理的是任意大的输入，而不仅仅是真正的编程语言支持的大到足以满足所有实际目的，而且这种差异很难调和（如此处）。

Answer 2

您刚刚错过了引用行之前的第一行：-

In the automata theory, a set of all palindromes in a given alphabet is a typical example of a language that is context-free, but not regular.

在这里，他们谈论的是列出给定字母表上所有可能的回文。

我们来谈谈二进制字母表，A={0,1}。考虑到语言 -> 字母表 A 上的回文数。可以有无限多个回文字符串，例如 1,0,11,00,101,111,... 等等。

在回文语言的情况下，至少不可能在同一次传递中获得中间元素的想法并将其保存在内存（轨道）中，在有限记忆系统中。为此，您需要跟踪正在评估的字符串的各种字符，以及如何确定传入字符是否与您访问过的字符相反，仅在有限内存系统中通过一次？

维基百科还指出：-

In addition, the set of palindromes may not be reliably tested by a deterministic pushdown automaton. When reading a palindrome from left-to-right, it is, in essence, impossible to locate the "middle" until the entire word has been read completely.

这种由所有此类字符串组成的语言无法在有限内存系统中一次通过评估，因此，由于有限内存限制，不能成为常规语言（a常规语言可以定义为有限自动机识别的语言---这种语言不能在有限内存系统中识别，因为有限内存系统不能有多次通过 ).因此，该语言无法评估所有这些字符串集的回文。因此，它显然是 有限内存系统 .

的示例

这个问题又回到了自动机理论的著名问题之一：-

对于语言 E，E = {0^i 1^j | i > j} 不是正则的。并且，因此无法在具有有限 memory.You 的机器上证明它需要泵送引理定理来证明给定的语言是不规则的。然后，您需要在此处放回下推自动机。但是，这也有它的局限性（先不说了）

此外，下一行显然是想说具有巨大内存和涉及许多遍的最新技术的现代计算机将很容易实现同样的目标--->

(For practical purposes with modern computers, this limitation would apply only to incredibly long letter-sequences.) // Again when the memory exhausts in the modern computers while checking for palindromes.

Answer 3

问题不在于检查内存中的字符串是否为回文。如果你能把字符串读入内存，检查就很容易了，但是你把字符串读入内存已经用完了一遍，所以检查是第二遍。

但这只有在整个字符串都适合内存时才有效。由于前提是内存是有限的，也就是说你无法验证长度超过内存容量的字符串是否是回文，这就是你引用的那句话。

相比之下，您可以使用有限的内存对任意长的字符串进行大量检查。例如，您可以检查字符串的长度是否可以被 5 整除。您可以检查字符串中的每个 a 是否紧跟一个 b。通常，您可以检查字符串是否匹配任何正则表达式（这里，我指的是数学意义上的正则表达式，而不是 "regular expression" 库识别的模式。）但是由于您无法描述所有回文的集合使用正则表达式，您无法一次性验证任意长的字符串是否为回文，仅使用有限的内存量。

为什么我们不能一次性可靠地测试回文

Why we can't reliably test for palindromes on one pass

string

algorithm

memory

palindrome

automata