介绍
在本教程中，我们讨论了一种使用输入字符串找到所有可能的回文子字符串的方法。为了实现这个任务的方法，我们使用C++编程语言及其函数。
回文是一种从前往后和从后往前读都一样的字符串。例如，Mom是一个回文字符串。在本教程中，我们将取一个字符串并找出其中所有可能的回文子字符串。
Example 1
的中文翻译为：
示例1
输出
The possible palindromic substrings are : a, b, c, aa, aaa, aba, and aca.
登录后复制
在上面的例子中，输入字符串可以生成7个回文子字符串：‘a’，‘b’，‘c’，‘aa’，‘aaa’，‘aba’和‘aca’。
Example 2
的中文翻译为：
示例2
输出
在上面的例子中，使用输入字符串只能得到4个长度为1的回文子串。由于输入字符串中没有重复的字符，因此没有任何子串的长度超过1。
用于示例实现的函数
语法
string_name.size();
登录后复制
示例
语法
示例
语法
string_name.substr(pos, len);
登录后复制
示例
算法
考虑一个给定的字符串，找出其中所有的回文子字符串。
通过迭代字符串，找到输入字符串的所有回文子字符串。
为奇数和偶数长度的回文子字符串创建两个数组。
将两个数组的值存储在哈希映射中。
打印存储在Hashmap中的所有值。
子字符串的数量等于哈希映射的长度。通过哈希映射进行迭代，并打印出每个值。使用for循环访问映射中的每个项，并打印其关联的值。最后，打印的值的数量应与哈希映射的大小相匹配。
Logic 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
登录后复制
Logic 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++编程语言编写了一个示例代码。我们使用哈希映射和向量来存储回文子字符串以实现示例。哈希映射的使用有助于匹配键值对，我们可以根据需要使用许多哈希函数。我们还使用了一些库函数来实现示例。
以上是使用动态规划找出给定字符串中的不同回文子串的详细内容。更多信息请关注PHP中文网其他相关文章！
