回文子串查询

2025年3月17日 | 阅读 7 分钟

给定一个字符串和一组查询，这些查询指定了包含首尾的范围，需要判断指定范围内的子串是否为回文。

考虑以下场景：我们有一个输入字符串 "abaaabaaaba" 和一组查询：[0, 10], [5, 8], [2, 5], [5, 9]。我们的任务是确定这些查询索引指定的子字符串是否为回文。

例如

[0, 10] corresponds to the substring "abaaabaaaba," which is a palindrome.
[5, 8] corresponds to the substring "baaa," which is not a palindrome.
[2, 5] corresponds to the substring "aaab," which is not a palindrome.
[5, 9] corresponds to the substring "baaab," which is a palindrome.

对于长度为 N 的输入字符串，解决 Q 个此类查询有两种主要方法：

方法1（朴素方法）

在这种方法中，我们单独遍历每个查询，并检查指定的子字符串是否为回文。由于有 Q 个此类查询，并且在最坏情况下，每个查询判断回文可能需要 O(N) 的时间，因此此方法的最坏时间复杂度为 O(Q * N)。虽然此方法节省空间，但存在更有效的替代方案。

该方法的 Java 实现

public class CheckPalindromeSubstrings {

    // A function to check if a string is a palindrome
    // in the range from left to right
    public static boolean isPalindromeSubstring(String input, int left, int right) {
        // Keep comparing characters while they are the same
        while (right > left) {
            if (input.charAt(left) != input.charAt(right))
                return false;
            left++;
            right--;
        }
        return true;
    }

    /* Driver program to test the isPalindromeSubstring function */
    public static void main(String[] args) {
        String inputStr = "abaaabaaaba";
        int strLength = inputStr.length();

        int[][] queries = {
            {0, 10},
            {5, 8},
            {2, 5},
            {5, 9}
        };

        for (int[] query : queries) {
            boolean result = isPalindromeSubstring(inputStr, query[0], query[1]);
            if (result)
                System.out.println("The substring [" + query[0] + "," + query[1] + "] is a palindrome");
            else
                System.out.println("The substring [" + query[0] + "," + query[1] + "] is not a palindrome");
        }
    }
}

输出

时间复杂度

检查每个子字符串的回文特性涉及比较左右两边的字符。

对于每个长度为 N 的子字符串的查询，时间复杂度为 O(N)。

如果总共有 Q 个查询，则整体时间复杂度为 O(Q * N)，其中 Q 是给定问题中的查询数量，N 是子字符串的最大长度。

空间复杂度

空间复杂度为 O(1)，因为程序使用的额外内存量不依赖于输入大小。无论输入字符串长度或查询数量如何，它只使用常量内存用于变量和数据结构。

方法2（累积哈希）

这种方法背后的概念类似于 Rabin-Karp 字符串匹配算法。它依赖于字符串哈希，涉及计算原始字符串和反转字符串的累积哈希值，并将它们存储在两个数组中：`prefix[]` 和 `suffix[]`。

溢出问题

即使对于小字符串，哈希值也可能变得非常大。

为避免溢出，代码对所有操作执行模 1000000007，这是一个出于数学原因选择的素数。这个素数适合整数值。

Java 和 Python 可以在没有模运算的情况下处理这些大值。

程序中使用的主要模运算是：

加法：(a + b) % M = (a % M + b % M) % M

乘法：(a * b) % M = (a * b) % M

加法和乘法混合：(a * x + b * y + c) % M = ((a * x) % M + (b * y) % M + c % M) % M

减法：(a - b) % M = (a % M - b % M + M) % M

除法：(a / b) % M = (a * MMI(b)) % M，其中 MMI() 计算模乘法逆元，由程序中的 `findMMI()` 函数实现。

Java 实现

public class PalindromeSubstring {

    // Structure to represent a query. A query consists
    // of (startIndex, endIndex), and we have to answer whether the substring
    // from index- startIndex to endIndex  is a palindrome or not
    static class Query {
        int startIndex, endIndex;

        Query(int startIndex, int endIndex) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }
    }

    static final int BASE = 101;
    static final int MODULO = 1000000007;

    // A function to check if a string str is a palindrome
    // in the range startIndex to endIndex
    static boolean isPalindrome(String str, int startIndex, int endIndex) {
        // Keep comparing characters while they are the same
        while (endIndex > startIndex) {
            if (str.charAt(startIndex++) != str.charAt(endIndex--)) {
                return false;
            }
        }
        return true;
    }

    // A Function to find (base ^ exponent) % MODULO
    // in log(exponent) time
    static long computeModularExponentiation(long base, long exponent) {
        if (exponent == 0)
            return 1;
        if (exponent == 1)
            return base;

        long result = computeModularExponentiation(base, exponent / 2);

        if (exponent % 2 == 0)
            return (result % MODULO * result % MODULO) % MODULO;
        else
            return (((result % MODULO * result % MODULO) % MODULO) * base % MODULO) % MODULO;
    }

    // A Function to calculate Modulo Multiplicative Inverse of 'n'
    static long findModuloMultiplicativeInverse(long n) {
        return computeModularExponentiation(n, MODULO - 2);
    }

    // A Function to calculate the prefix hash
    static void computePrefixHash(String str, int length, long prefixHash[], long powersOfBase[]) {
        prefixHash[0] = 0;
        prefixHash[1] = str.charAt(0);

        for (int i = 2; i <= length; i++) {
            prefixHash[i] = (prefixHash[i - 1] % MODULO
                    + (str.charAt(i - 1) % MODULO
                            * powersOfBase[i - 1] % MODULO)
                    % MODULO)
                    % MODULO;
        }
    }

    // A Function to calculate the suffix hash
    // Suffix hash is nothing but the prefix hash of
    // the reversed string
    static void computeSuffixHash(String str, int length, long suffixHash[], long powersOfBase[]) {
        suffixHash[0] = 0;
        suffixHash[1] = str.charAt(length - 1);

        for (int i = length - 2, j = 2; i >= 0 && j <= length; i--, j++) {
            suffixHash[j] = (suffixHash[j - 1] % MODULO
                    + (str.charAt(i) % MODULO
                            * powersOfBase[j - 1] % MODULO)
                    % MODULO)
                    % MODULO;
        }
    }

    // A Function to answer the Queries
    static void answerQueries(String str, Query queries[], int queryCount, int stringLength, long prefixHash[], long suffixHash[], long powersOfBase[]) {
        for (int i = 0; i < queryCount; i++) {
            int startIndex = queries[i].startIndex;
            int endIndex = queries[i].endIndex;

            // Hash Value of Substring [startIndex, endIndex]
            long hashValue = ((prefixHash[endIndex + 1] - prefixHash[startIndex] + MODULO) % MODULO
                    * findModuloMultiplicativeInverse(powersOfBase[startIndex]) % MODULO)
                    % MODULO;

            // Reverse Hash Value of Substring [startIndex, endIndex]
            long reverseHashValue = ((suffixHash[stringLength - startIndex] - suffixHash[stringLength - endIndex - 1] + MODULO) % MODULO
                    * findModuloMultiplicativeInverse(powersOfBase[stringLength - endIndex - 1]) % MODULO)
                    % MODULO;

            // If both are equal, then
            // the substring is a palindrome
            if (hashValue == reverseHashValue) {
                if (isPalindrome(str, startIndex, endIndex))
                    System.out.println("The Substring [" + startIndex + " " + endIndex + "] is a palindrome");
                else
                    System.out.println("The Substring [" + startIndex + " " + endIndex + "] is not a palindrome");
            } else
                System.out.println("The Substring [" + startIndex + " " + endIndex + "] is not a palindrome");
        }
    }

    // A Dynamic Programming Based Approach to compute the
    // powers of 101
    static void computePowersOfBase(long powersOfBase[], int length) {
        // BASE^0 = 1
        powersOfBase[0] = 1;

        for (int i = 1; i <= length; i++) {
            powersOfBase[i] = (powersOfBase[i - 1] % MODULO * BASE % MODULO) % MODULO;
        }
    }

    public static void main(String[] args) {
        String str = "abaaabaaaba";
        int stringLength = str.length();

        // A Table to store the powers of 101
        long[] powersOfBase = new long[stringLength + 1];

        computePowersOfBase(powersOfBase, stringLength);

        // Arrays to hold prefix and suffix hash values
        long[] prefixHash = new long[stringLength + 1];
        long[] suffixHash = new long[stringLength + 1];

        // Compute Prefix Hash and Suffix Hash Arrays
        computePrefixHash(str, stringLength, prefixHash, powersOfBase);
        computeSuffixHash(str, stringLength, suffixHash, powersOfBase);

        Query[] queries = {new Query(0, 10), new Query(5, 8), new Query(2, 5), new Query(5, 9)};
        int queryCount = queries.length;

        answerQueries(str, queries, queryCount, stringLength, prefixHash, suffixHash, powersOfBase);
    }
}

输出

工作方式

输入

字符串："abbaaba"

查询：[0, 6], [1, 4], [2, 5], [0, 3]

步骤1：常量和辅助函数

BASE 设置为 101。

MODULO 设置为 1000000007。

步骤2：预计算 BASE 的幂

我们预计算一个 BASE 幂的数组，以实现高效哈希。对于此示例，假设 `powersOfBase` 是 [1, 101, 101^2, ..., 101^6]。

步骤3：计算前缀和后缀哈希

我们计算两个数组：

`prefixHash`：存储原始字符串 "abbaaba" 的哈希值。

`suffixHash`：存储反转字符串 "abaabba" 的哈希值。

假设这些数组填充如下：

`prefixHash`：[0, 97, 10098, ..., HashValueAtIndexN]

`suffixHash`：[0, 97, 10098, ..., HashValueAtIndexN]

这些数组是使用模算术和 BASE 的幂计算的。

步骤4：处理查询

我们有四个查询，我们希望确定指定的子字符串是否为回文。

查询1：[0, 6]

使用 `prefixHash` 和 `powersOfBase` 计算子字符串 "abbaaba" 的哈希值。

使用 `suffixHash` 和 `powersOfBase` 计算反转子字符串 "abaabba" 的哈希值。

比较哈希值。如果它们匹配，则使用 `isPalindrome` 比较字符。在此情况下，它们匹配，因此它是回文。

查询2：[1, 4]

使用 `prefixHash` 和 `powersOfBase` 计算子字符串 "bbaa" 的哈希值。

使用 `suffixHash` 和 `powersOfBase` 计算反转子字符串 "aabb" 的哈希值。

比较哈希值。它们不匹配，因此它不是回文。

查询3：[2, 5]

类似于查询2，计算子字符串 "baab" 及其反转的哈希值。

同样，哈希值不匹配，因此它不是回文。

查询4：[0, 3]

使用 `prefixHash` 和 `powersOfBase` 计算子字符串 "abba" 的哈希值。

使用 `suffixHash` 和 `powersOfBase` 计算反转子字符串 "abba" 的哈希值。

哈希值匹配，并且 `isPalindrome` 确认它是回文。

时间复杂度： O(n*m)

空间复杂度：O(n)

下一主题Recaman序列

回文子串查询

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

回文子串查询

相关帖子

数据结构中的跳表

数据结构中的反转对问题

二叉搜索树实现

Java 语言中移除 BST 范围外的键

什么是 K 连通图

自平衡二叉搜索树

下一个回文数

O(N^2) 复杂度意味着什么

股票收益问题

查找两个大小写字母中都存在的最大英文字母

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器