在本教程中，我们需要解决给定字符串的回文子串查询。解决回文子串查询比解决 c++ 中的常规查询复杂得多。它需要更复杂的代码和逻辑。
在本教程中，我们提供了字符串 str 和 q 个子字符串 [l...r] 查询，每个查询都有两个值 l 和 r。我们的目标编写一个程序来解决查询以确定 substring[l...r] 是否是回文。我们必须确定在 l 到 r 范围内形成的子串是否是回文来解决每个查询。例如 -
let's input "abbbabaaaba" as our input string.the queries were [3, 13], [3, 11], [5, 8], [8, 12]it is necessary to determine whether the substring is a plaindromea palindrome is "abaaabaaaba" (3, 13) .it is not possible to write "baaa" as a palindrome [3, 11].as in [5, 8]: "aaab" cannot be a palindrome.there is a palindrome in "baaab" ([3, 12]).
求解的方法朴素方法
这里，我们必须通过检查子字符串是否在索引范围 l 到 r 之间来查找回文因此，我们需要对所有的子串查询进行一一检查，判断是否是回文。由于有 q 个查询，每个查询需要 0(n) 时间来回答。最坏情况下需要 0(q.n) 时间。
示例#include <bits/stdc++.h>using namespace std;int ispallindrome(string str){ int i, length; int flag = 0; length = str.length(); for(i=0;i < length ;i++){ if(str[i] != str[length-i-1]) { flag = 1; break; } } if (flag==1) return 1; return 0;}void solveallqueries(string str, int q, int query[][2]){ for(int i = 0; i < q; i++){ ispallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))? cout<<"palindrome\n":cout<<"not palindrome!\n"; }}int main() { string str = "abccbeba"; int q = 3; int query[q][2] = {{3, 5}, {5, 7}, {2, 1}}; solveallqueries(str, q, query); return 0;}
输出palindromepalindromenot palindrome!
动态规划方法使用动态规划方法来解决问题是一种有效的选择。为了解决这个问题，我们需要创建一个 dp 数组，它是一个二维数组，其中包含一个布尔值，指示 substring[i...j] 是否是 dp[i][j] 的回文。将创建此 dp 矩阵，并检查每个查询的所有 l-r 值。
示例#include <bits/stdc++.h>using namespace std;void computedp(int dp[][50], string str){ int length = str.size(); int i, j; for (i = 0; i < length; i++) { for (j = 0; j < length; j++) dp[i][j] = 0; } for (j = 1; j <= length; j++) { for (i = 0; i <= length - j; i++) { if (j <= 2) { if (str[i] == str[i + j - 1]) dp[i][i + j - 1] = 1; } else if (str[i] == str[i + j - 1]) dp[i][i + j - 1] = dp[i + 1][i + j - 2]; } }}void solveallqueries(string str, int q, int query[][2]){ int dp[50][50]; computedp(dp, str); for(int i = 0; i < q; i++){ dp[query[i][0] - 1][query[i][1] - 1]?cout <<"not palindrome!\n":cout<<"palindrome!\n"; }}int main() { string str = "abccbeba"; int q = 3; int query[q][2] = {{3, 5}, {5, 7}, {2, 1}}; solveallqueries(str, q, query); return 0;}
输出palindrome!not palindrome!palindrome!
结论在本教程中，我们学习了如何使用 c++ 代码解决回文子串查询。我们还可以用java、python和其他语言编写这段代码。这段代码是最复杂、最冗长的代码之一。回文查询比常规子串查询更难，并且需要非常准确的逻辑。我们希望本教程对您有所帮助。
以上就是回文子字符串查询在c++中的详细内容。