数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 中回文子串查询
在本教程中，我们需要解决给定字符串的回文子串查询问题。解决回文子串查询比在 C++ 中解决常规查询要复杂得多。它需要更复杂的代码和逻辑。
在本教程中，我们提供了字符串 str 和 Q 个子串 [L...R] 查询，每个查询有两个值 L 和 R。我们的目标是编写一个程序来解决查询，以确定子串 [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 plaindrome A 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;
}输出
Palindrome Palindrome Not palindrome!
动态规划方法
使用动态规划方法来解决这个问题是一种有效的选择。为了解决这个问题，我们需要创建一个 DP 数组，这是一个二维数组，包含一个布尔值，指示子串 [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 和其他语言编写此代码。这段代码是最复杂和最冗长的代码之一。回文查询比常规子串查询更难，需要非常精确的逻辑。我们希望本教程对您有所帮助。
更新于：2022年3月7日
448 次浏览
广告