在本教程中，我們需要解決給定字串的回文子字串查詢。解決回文子字串查詢比解決 C 中的常規(guī)查詢複雜得多。它需要更複雜的程式碼和邏輯。

在本教程中，我們提供了字串 str 和 Q 個(gè)子字串 [L...R] 查詢，每個(gè)查詢都有兩個(gè)值 L 和 R。我們的目標(biāo)編寫一個(gè)程式來(lái)解決查詢以確定 substring[L...R] 是否是回文。我們必須確定在 L 到 R 範(fàn)圍內(nèi)形成的子字串是否為回文來(lái)解決每個(gè)查詢。例如-

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]).

求解的方法

樸素方法

這裡，我們必須透過(guò)檢查子字串是否在索引範(fàn)圍L 到R 之間來(lái)查找回文因此，我們需要對(duì)所有的子字串查詢進(jìn)行一一檢查，判斷是否是回文。由於有 Q 個(gè)查詢，每個(gè)查詢需要 0(N) 時(shí)間來(lái)回答。最壞情況下需要 0(Q.N) 時(shí)間。

範(fà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!

動(dòng)態(tài)規(guī)劃方法

使用動(dòng)態(tài)規(guī)劃方法來(lái)解決問(wèn)題是有效的選擇。為了解決這個(gè)問(wèn)題，我們需要建立一個(gè) DP 數(shù)組，它是一個(gè)二維數(shù)組，其中包含一個(gè)布林值，指示 substring[i...j] 是否是 DP[i][j] 的回文。

將建立此 DP 矩陣，並檢查每個(gè)查詢的所有 L-R 值。

範(fàn)例

#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!

結(jié)論

在本教學(xué)中，我們學(xué)習(xí)如何使用 C 程式碼解決回文子字串查詢。我們也可以用java、python和其他語(yǔ)言來(lái)寫這段程式碼。這段程式碼是最複雜、最冗長(zhǎng)的程式碼之一?；匚牟樵儽瘸Ｒ?guī)子字串查詢更難，並且需要非常準(zhǔn)確的邏輯。我們希望本教學(xué)對(duì)您有所幫助。

以上是回文子字串查詢?cè)贑++中的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！