C++ の回文部分文字列クエリ

このチュートリアルでは、指定された文字列の回文部分文字列クエリを解決する必要があります。回文部分文字列クエリの解決は、C で通常のクエリを解決するよりもはるかに複雑です。より複雑なコードとロジックが必要になります。

このチュートリアルでは、それぞれ 2 つの値 L と R を持つ string str クエリと Q substring [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 までの間にあるかどうかを確認する必要があります。回文を見つけるには、すべての部分文字列クエリを 1 つずつチェックして、回文であるかどうかを判断する必要があります。 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 配列を作成する必要があります。これは、substring[i...j] が DP[i][j] の回文であるかどうかを示すブール値を含む 2 次元配列です。

この 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、その他の言語でも記述できます。このコードは、最も複雑で冗長なコードの 1 つです。回文クエリは通常の部分文字列クエリよりも難しく、非常に正確なロジックが必要です。このチュートリアルがお役に立てば幸いです。

以上がC++ の回文部分文字列クエリの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。