回文子串是指正序和倒序相同的一段字符串，如“aba”、“abba”等。在 C++ 中，我们可以使用多种方法输出一段字符串中的回文子串。

方法一：暴力枚举法

暴力枚举法是最简单直接的方法，通过枚举字符串的起始位置和结束位置，判断该子串是否为回文子串。具体实现如下：

#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string s, int i, int j) {
  while (i < j) {
    if (s[i++] != s[j--])
      return false;
    
  }
  return true;
}
void PalindromicSubstring(string s) {
  int len = s.size();
  for (int i = 0; i < len; i++) {
    for (int j = i; j < len; j++) {
      if (isPalindrome(s, i, j)) {
        cout << s.substr(i, j - i + 1) << endl;
      }
    }
  }
}
int main() {
  PalindromicSubstring("abbcbaab");
  return 0;
}

方法二：动态规划法

动态规划法是一种高效且常用的方法，通过构建一个二维表格，记录字符串中每个位置的回文状态，并将其转移出到其它位置。具体实现如下：

#include <bits/stdc++.h>
using namespace std;
void PalindromicSubstring(string s) {
  int n = s.size();
  bool dp[n][n];
  memset(dp, false, sizeof(dp));
  int maxlen = 1, start = 0;
  for (int i = 0; i < n; i++) {
    dp[i][i] = true;
  }
  for (int i = 0; i < n - 1; i++) {
    if (s[i] == s[i + 1]) {
      dp[i][i + 1] = true;
      maxlen = 2;
      start = i;
    }
  }
  for (int len = 3; len <= n; len++) {
    for (int i = 0; i < n - len + 1; i++) {
      int j = i + len - 1;
      if (s[i] == s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        if (len > maxlen)
          maxlen = len;
          start = i;
        
      }
    }
  }
  for (int i = start; i < start + maxlen; i++) {
    cout << s[i];
  }
  cout << endl;
}
int main() {
  PalindromicSubstring("abbcbaab");
  return 0;
}

不管是暴力枚举法还是动态规划法，都能够有效地输出回文子串，但是在实际项目中应该尽可能使用更高效的算法，以提升程序的运行效率。

相似文章
• 探究Java经典算法面试题
  探究Java经典算法面试题
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政