在本教程中,我們討論了一種使用輸入字串找到所有可能的回文子字串的方法。為了實現這個任務的方法,我們使用C 程式語言及其函數。
回文是一種從前往後和從後往前讀都一樣的字串。例如,Mom是一個回文字串。在本教程中,我們將取一個字串並找出其中所有可能的回文子字串。
String = abcaa
The possible palindromic substrings are : a, b, c, aa, aaa, aba, and aca.
在上面的例子中,輸入字串可以產生7個回文子字串:‘a’,‘b’,‘c’,‘aa’,‘aaa’,‘aba’和‘aca’。
String = “abcd”
a, b, c, and d.
在上面的範例中,使用輸入字串只能得到4個長度為1的回文子字串。由於輸入字串中沒有重複的字符,因此沒有任何子字串的長度超過1。
size() − 這是一個字串類別函數,傳回給定字串中字元的數量。它不接受參數。
string_name.size();
str.size();
begin() − 這個函式庫函數在STL中定義。它給出了map容器的起始迭代值。
end() − 這個函式庫函數在STL中定義。它給出了map容器的結束迭代值。
map_name.end();
mp.end();
substr() − 它使用輸入字串產生一個子字串。它在string.h頭檔中定義。它接受兩個參數(pos,len)。 Pos是子字串的起始值,len是子字串中的字元數。
string_name.substr(pos, len);
str.substr();
考慮一個給定的字串,找出其中所有的回文子字串。
透過迭代字串,找到輸入字串的所有回文子字串。
為奇數和偶數長度的回文子字串建立兩個陣列。
將兩個陣列的值儲存在雜湊映射中。
列印儲存在Hashmap中的所有值。
子字串的數量等於雜湊映射的長度。透過哈希映射進行迭代,並列印出每個值。使用for循環存取映射中的每個項,並列印其關聯的值。最後,列印的值的數量應與哈希映射的大小相符。
在這個部分中,我們使用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
我們正在使用動態規劃方法實作另一個範例。在動態規劃中,任務被分解為子任務並單獨解決,以減少時間和複雜度。
#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 程式語言編寫了一個範例程式碼。我們使用哈希映射和向量來儲存回文子字串以實現範例。哈希映射的使用有助於匹配鍵值對,我們可以根據需要使用許多雜湊函數。我們也使用了一些函式庫函數來實作範例。
以上是使用動態規劃找出給定字串中的不同回文子串的詳細內容。更多資訊請關注PHP中文網其他相關文章!