C++プログラムでsubstring[L…R]が回文であるかどうかを確認するためのクエリ

この問題では、文字列str、substring [L...R]の2つの値LとRでそれぞれ構成されるクエリのQ数が与えられます。私たちのタスクは、サブストリング[L…R]が回文であるかどうかをチェックするためにクエリを解決するプログラムを作成することです。

問題の説明 −各クエリを解決するには、LからRの範囲内で作成された部分文字列が回文であるかどうかを確認する必要があります。

問題を理解するために例を見てみましょう

入力

str = “abccbeba” , Q = 3
Query[][] = {{1, 4}, {0, 6}, {4, 6}}

出力

Palindrome
Not Palindrome
Palindrome

説明

Creating all substring for the given
substrings : Substring[1...4] = “bccb”, it is a palindrome
Substring[0...6] = “abccbeb”, it is a not palindrome
Substring[4...6] = “beb”, it is a palindrome

ソリューションアプローチ

この問題の簡単な解決策は、各クエリを解決することです。これを解決するには、インデックス範囲LからRまでの部分文字列を見つける必要があります。そして、部分文字列が回文であるかどうかを確認します。

ソリューションの動作を説明するプログラム

例

#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] = {{1, 3}, {2, 5}, {4, 5}};
   solveAllQueries(str, Q, query);
   return 0;
}

出力

Palindrome
Not palindrome!
Palindrome

これは単純なアプローチですが、効率的なアプローチではありません。

この問題の効率的な解決策は、動的計画法のアプローチを使用することです。解くには、サブストリング[i...j]がDP[i][j]の回文であるかどうかを示すブール値を格納する2次元配列のDP配列を作成する必要があります。

この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] = {{1, 3}, {2, 5}, {4, 5}};
   solveAllQueries(str, Q, query);
   return 0;
}

出力

palindrome!
not palindrome!
palindrome!