資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用動態規劃查詢給定字串的不同迴文子串
介紹
在本教程中，我們將討論一種使用輸入字串查詢所有可能的迴文子串的方法。為了實現此任務的方法，我們將使用C++程式語言及其函式。
迴文是指從後往前讀和從前往後讀都一樣的字串。例如，“Mom”就是一個迴文串。在本教程中，我們將取一個字串，並從中查詢所有可能的迴文子串。
示例1
String = abcaa
輸出
The possible palindromic substrings are : a, b, c, aa, aaa, aba, and aca.
在上面的示例中，輸入字串可以構成7個迴文子串：“a”、“b”、“c”、“aa”、“aaa”、“aba”和“aca”。
示例2
String = “abcd”
輸出
a, b, c, and d.
在上面的示例中，使用輸入字串，只有4個長度為1的迴文子串。由於輸入字串中沒有重複字元，因此沒有哪個子串的長度超過1。
示例實現中使用的函式
size() − 這是一個字串類函式，它返回字串的長度，計算給定字串中的字元數。它不接受引數。
語法
string_name.size();
示例
str.size();
begin() − 此庫函式在STL中定義。它給出map容器的起始迭代值。
語法：map_name.begin(); 示例：mp.begin();end() − 此庫函式在STL中定義。它給出map容器的結束迭代值。
語法
map_name.end();
示例
mp.end();
substr() − 它使用輸入字串生成子字串。它在string.h標頭檔案中定義。它接受兩個引數 (pos, len)。Pos是子字串的起始值，len是子字串中的字元數。
語法
string_name.substr(pos, len);
示例
str.substr();
演算法
考慮給定一個字串以查詢其所有迴文子串。
透過迭代字串來查詢輸入字串的所有迴文子串。
為奇數長度和偶數長度的迴文子串建立兩個陣列。
將這兩個陣列的值儲存在雜湊表中。
列印儲存在雜湊表中的所有值。
子串的數量等於雜湊表的長度。遍歷雜湊表並列印每個值。使用for迴圈訪問map中的每個專案並列印其關聯的值。最後，列印的值的數量應與雜湊表的size匹配。
邏輯示例1
在本節中，我們將使用C++程式語言的概念來實現上述示例之一。我們考慮main()函式中的輸入字串並使用它來生成輸出。
#include <iostream>
#include <map>
using namespace std;
//user defined program to find the palindrome substrings
void palindromeSubStrings(string str){
map<string, int> mp;
int l = str.size();
//store odd and even length palindrome substrings
int R[2][l+1];
//Using guards for effortless iteration over the input string and generating all palindrome
// substrings
str = "@" + str + "#";
for (int i = 0; i <= 1; i++) {
int r = 0;
R[i][0] = 0;
int x = 1;
while (x <= l){
while (str[x - r - 1] == str[x + i + r])
r++;
R[i][x] = r;
int a = 1;
while ((R[i][x - a] != r - a) && (a < r)){
R[i][x + a] = min(R[i][x - a],r - a);
a++;
}
r = max(r - a,0);
x += a;
}
}
//storing the substring without guards
str = str.substr(1, l);
mp[string(1, str[0])]=1;
for (int x = 1; x <= l; x++){
for (int y = 0; y <= 1; y++)
for (int r = R[y][x]; r > 0; r--)
mp[str.substr(x - r - 1, 2 * r + y)]=1;
mp[string(1, str[x])]=1;
}
//print the palindrome substrings stored in the Hashmap
cout << "Palindrome substrings are as listed: ";
map<string, int>::iterator xx;
for (xx = mp.begin(); xx!=mp.end(); ++xx)
cout << (*xx).first << endl;
}
//Controlling code
int main(){
//calling the user-defined function and passing a string as argument
palindromeSubStrings("abcaa");
return 0;
}
輸出
Palindrome substrings are listed as: a aa b c
邏輯示例2
我們將使用動態規劃方法實現另一個示例。在動態規劃中，任務被劃分為子任務，並分別解決以減少時間和複雜性。
#include <iostream>
#include <vector>
using namespace std;
//User defined function to find the palindromic substring
int find(string str){
int a = str.size();
//defined dpg array
vector<vector<bool> > dpg(a, vector<bool>(a, false));
for (int x = 0; x < a; x++) {
dpg[x][x] = 1;
if (x < a && str[x] == str[x + 1]) {
dpg[x][x + 1] = 1;
}
}
// Finding length of different substrings
for (int l = 3; l <= a; l++) {
for (int x = 0; x + l - 1 < a; x++){
if (str[x] == str[x + (l - 1)]
&& dpg[x + 1][x + (l - 1) - 1]) {
dpg[x][x + (l - 1)] = true;
}
}
}
vector<int> kmp(a, 0);
for (int x = 0; x < a; x++) {
int y = 0, m = 1;
while (m + x < a) {
if (str[y + x] == str[m + x]){
dpg[m + x - y][m + x] = false;
kmp[m++] = ++y;
}
else if (y > 0) {
y = kmp[y - 1];
}
else {
kmp[m++] = 0;
}
}
}
int cnt = 0;
for (int x = 0; x < a; x++) {
string str1;
for (int y = x; y < a; y++) {
str1 += str[y];
if (dpg[x][y]) {
//counting number of palindromic substrings formed using the string
cnt++;
cout << str1 << '\n';
}
}
}
cout << "Total number of palindromes are "
<< cnt << '\n';
return 0;
}
//Controller
int main(){
string str = "abaa";
find(str);
return 0;
}
輸出
a aba b aa Total number of palindromes are 4
結論
在本教程中，我們開發了兩種方法來查詢給定字串中所有可能的迴文子串。我們透過兩個示例來理解任務，並使用C++程式語言編寫一個示例。我們使用雜湊表和向量來儲存迴文子串以實現示例。雜湊表的使用有助於匹配鍵值對，我們可以根據需要使用許多雜湊函式。我們還使用了一些庫函式來實現該示例。
395 次瀏覽
