如何检测回文的第一次出现

Question

假设您正在从字符流中读取，当您读取第一个回文出现时，函数应该返回。

回文的长度应为偶数。

时间复杂度要求为O(N)。

示例：

1. 第一个字符：4 2. 第二个字符：1 3. 第三个字符：3 4. 第四个字符：3 5. 第五个字符：1 6. 第六个字符：4，返回结果。

- Kan

---

什么是第一次出现？ - SMK

必须超过一个字符吗？“读取第一个字符，返回”。必须使用整个字符串吗？例如，“4, 1, 3, 3”会返回，因为“3,3”是回文。 - jb.

当输入流为413314时，您可以阅读我的示例。它应该在读取第6个字符时停止，因为413314是一个回文，而4、41、413、4133、41331则不是。 - Kan

@jb。是的，它必须是整个字符串。 - Kan

您能保证回文的第一个字符是输入流的第一个字母吗？或者回文可以从任意位置开始吗？ - oksayt

Answer 1

在大多数情况下，应该以线性时间O(n)运行的一个近似解决方案是使用滚动哈希。您需要跟踪字符串及其反转的哈希值。每次读取一个新字符时，可以在O(1)时间内更新两个哈希值。然后，您比较这两个哈希值，如果它们相等，则比较字符串和其反转。如果也相等，则退出并得到一个回文。例如，一个非常简单的滚动哈希函数是哈希（ck c(k-1).. c0）=（p^k*ck + p^(k - 1) * c(k - 1) + ... + c0）mod m，其中p是奇素数。因此，从以下内容开始：

p = 17 // or your lucky prime number
m = 10^9 // ...
hash = 0
hash_rev = 0
str = ''
str_rev = ''
p_pow = 1    

while True
    read c
    append c to str
    prepend c to str_rev
    hash = (hash * p + c) mod m
    hash_rev = (hash_rev + p_pow * c) mod m
    p_pow = p_pow * p
    if hash == hash_rev
         if str == str_rev
             found str to be the first palindrome

为了让它更快，你可以声明你的hash和hash_rev为32位整数，并选择m = 2^32。然后你可以忽略(mod m)操作。

- Pinch

---

如果第一个回文不是以流的开头开始呢？想象一下，第一个回文从流的第N个字符开始 - 那么你不需要一个哈希数组，每个哈希都从不同的点开始，并且你必须扫描每个可能成为回文字符串起始点的哈希吗？ - D Mac

这个问题的作者说回文必须是整个字符串，对吗？不过我可能错了。 - Pinch

Answer 2

当你读到第一个字符时，请返回，即是单字母回文。

- oksayt

---

请更新我的问题，使回文的长度为偶数。 - Kan

一个空字符串也是回文，0 是偶数，使用这种方法，你甚至不需要读取第一个字符。 - amit

@KanWu，如果字符串是2231322-那么返回结果是22，这样可以吗？ - Bill Cheatham

@BillCheatham 应该在问题的评论中提出。是的，它应该在22之后返回。 - kilotaras

@kilotaras，我正在试图澄清Kan Wu在此处给出的评论，并了解在新的约束条件下是否仍然可以接受像这个答案中给出的简单解决方案。 - Bill Cheatham

Answer 3

你需要的是对 Manacher算法 的微小修改。这个算法能够在线性时间内找到字符串中的所有回文子串。关于该算法，它实际上是从左到右进行处理，并在需要时“使用”新字符。所需的修改是，你只有在尝试访问新字符时才需要读取它。
如果找到一条回文路径一直回到流的开头，请停止。

- kilotaras

---

我在这个页面上读到了Manacher算法，但我不确定如何将Manacher算法应用于此问题，因为在计算“P[i]”时它必须更新“right”指针，并且需要在读取字符之前知道字符是什么。 - Kan

Answer 4

这段（未经测试的C#）代码可以实现，但我认为它可能是O(n^2)。有人能否确认/否认一下？

main()
{
    string str = "";
    char c1;
    char c2;

    while(true)
    {
        //has to be even, always get two chars at a time
        c1 = GetCharFromStream();
        c2 = GetCharFromStream();
        str += c1 + c2;
        if(isPalindrome(str))
        {
            Console.WriteLine(str);
            return;
        }
    }
}

bool isPalindrome(string str)
{
    if (str.Length % 2 != 0)
        throw new InvalidArgumentException("str");

    int first = 0;
    int last = str.Length - 1;

    while(first <= last)
    {
        if(str[first] != str[last])
            return false;

        first++;
        last--;
    }

    return true;
}

- jb.

---

当然是O(n^2)。每读取一个字符，就要遍历整个字符串以确定它是否为回文。 - WeaselFox

@WeaselFox，没错，这就是我想的。我的大O功夫还很弱。 - jb.

Answer 5

使用Hashset怎么样？

假设输入流是1221。

Hashset = empty;

if(hashset does not contain the inputelement)
{
   add to hashset. // 12 will be in the hashset. //413 for your example.
}

else
{
  delete from Hashset. // First deletes 2 and then 1. // First deletes 3, then 1 then 4.

  if(hashset is empty)
    return true; //Hashset is empty. return true.
}

- Sandeep

Answer 6

这是我的看法。它在每个新符号从字符串的当前中间位置开始扫描累积字符串，因此如果当前字符串不是回文，它将快速失败。

class PalindromeDetector {
    private static class DetectorImpl {
        final ArrayList<Character> string = new ArrayList<Character>(32);

        boolean addSymbol(char symbol) {
            string.add(symbol);
            return check();
        }

        private boolean check() {
            if (string.size() < 2)
                return false;

            int lowBound = string.size() / 2 - 1;
            int hiBound = lowBound + 1;
            while (lowBound >= 0 && string.get(lowBound) == string.get(hiBound)) {
                lowBound --; hiBound ++;
            }
            return lowBound == -1;
        }
    }

    static boolean isPalindrome(String s) {
        DetectorImpl detector = new DetectorImpl();
        int index = 0;
        while (index < s.length())
            if (detector.addSymbol(s.charAt(index++)))
                return true;
        return false;
    }
}

以下是用于该代码的单元测试：

@Test
public void test() {
    assertFalse(PalindromeDetector.isPalindrome("4"));
    assertTrue(PalindromeDetector.isPalindrome("44"));

    assertFalse(PalindromeDetector.isPalindrome("4343"));
    assertTrue(PalindromeDetector.isPalindrome("4334"));

    assertFalse(PalindromeDetector.isPalindrome("41331"));
    assertTrue(PalindromeDetector.isPalindrome("413314"));
}

- Victor Sorokin

Answer 7

好的，既然我的第一个答案时间复杂度是O(n^2)，那么这里有另一个答案，时间复杂度为O(n)，正如所请求的。

class PalindromeDetector {
    private static class DetectorImpl {
        int firstHalfSum, secondHalfSum;
        int size = 0, tensPower = 1;

        boolean add(int v) {
            if (size % 2 == 1) {
                firstHalfSum = firstHalfSum + (secondHalfSum / tensPower) * tensPower;
                secondHalfSum = (secondHalfSum % tensPower) * 10 + v;
                if (firstHalfSum == secondHalfSum)
                    return true;
            } else {
                secondHalfSum = secondHalfSum * 10 + v;
            }

            size ++;
            if (size % 2 == 0)
                tensPower *= 10;

            return false;
        }
    }

    static boolean isPalindrome(String s) {
        if (s == null || s.length() == 0)
            return false;

        int val = Integer.parseInt(s);
        int tensPower = s.length() == 1 ? 1 : (int) (Math.pow(10, s.length() - 1));
        DetectorImpl detector = new DetectorImpl();
        while (tensPower > 0) {
            int digit = val / tensPower;
            if (detector.add(digit))
                return true;

            val = val % tensPower;
            tensPower /= 10;
        }

        return false;
    }
}

这里是单元测试：

@Test
public void test() {
    assertFalse(PalindromeDetector.isPalindrome("4113"));
    assertTrue(PalindromeDetector.isPalindrome("3443"));
    assertTrue(PalindromeDetector.isPalindrome("473374"));
    assertTrue(PalindromeDetector.isPalindrome("413314"));
}

假设输入由十进制数字组成，但可以轻松扩展为包含字母数字的输入（只需假设英文字母+ 10个数字给我们提供了36进制的数字系统）。

- Victor Sorokin

Answer 8

这个解决方案（使用Haskell语言）依赖于一个观察结果，即偶数长度的回文串在其中心包含一个重复字符。当我们从输入流中读取字符时，我们测试这样的字符对，当找到一个时，我们就会生成一个新的候选答案。对于每个候选回文串，我们还保留一个“待匹配字符列表”，当读取每个新字符时，我们将其与该列表进行匹配 - 如果没有匹配，则丢弃该候选项。当匹配列表为空时，解决方案已经找到。请注意，尽管每个候选者都维护自己的匹配列表，但这些列表都只是同一列表的后缀，在Haskell中，即使有许多候选者，它们也将共享空间，并且总共不会占用超过O(n)的空间。

在最佳情况下，答案的中心只有一个成对字符，因此没有“误报”候选项，时间复杂度为O(n) - 每个字符最多被检查两次。对于具有许多错误开始的输入字符串，例如“abbbbbbbbbbbba”，我不确定时间复杂度 - 它可能不再是O(n)，但它比O(n^2)更好，因为没有候选项的存活时间超过min(k, n-k)，其中k是候选项中心的位置。

filter_map::(a -> Maybe a)->[a]->[a]
filter_map op = foldr (maybeCons . op) []
  where maybeCons Nothing  ys = ys
        maybeCons (Just y) ys = y:ys

-- Return the first prefix of the input argument that
-- is an even-length palindrome.
prefix_palindrome::(Eq a)=>[a]->[a]
prefix_palindrome (x:xs) = search [x] [] xs
  where search seen ([]:_) _ = seen
        search (s:seen) candidates (x:xs) | x == s = search seen' (candidates' ++ [seen]) xs
                                          | otherwise = search seen' candidates' xs
          where seen' = (x:s:seen)
                candidates' = filter_map extend candidates
                              where extend (c:cs) | c == x = Just cs
                                                  | otherwise = Nothing

- gcbenison