首页　>　文章列表　>　回文子字符串查询在C++中

回文子字符串查询在C++中

查询回文子字符串
293 2023-09-03

在本教程中，我们需要解决给定字符串的回文子串查询。解决回文子串查询比解决 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 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<<"Palindromen":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 数组，它是一个二维数组，其中包含一个布尔值，指示 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;
}