資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告