C++实现最长回文子串算法 |21xrx.com

C++实现最长回文子串算法

2023-06-25 18:53:05 深夜i 12 0

C++ 最长回文子串算法实现

最长回文子串算法是一个十分重要的字符串算法，C++语言在实现这个算法上也有其独特的方法。本文将会详细介绍在C++中如何实现最长回文子串算法。

一、算法思想

最长回文子串算法的思想是从中心往外扩展，每次比较左右两边的字符是否相同，直到左右两边字符不相同为止。具体来说，我们可以以下面的代码为基础：

int expandAroundCenter(string s, int left, int right) {
  int L = left, R = right;
  while (L >= 0 && R < s.size() && s[L] == s[R]) {
    L--;
    R++;
  }
  return R - L - 1;
}

这段代码的作用是从中心向两边扩展，求出以left和right为中心的最长回文子串长度。其中，L和R分别表示左右两个指针指向的位置。

二、实现过程

1. 先以每个字符为中心，调用expandAroundCenter函数，求出以该字符为中心的最长回文子串长度。

string longestPalindrome(string s) {
  int n = s.size();
  if (n < 2) return s;
  int start = 0, maxLength = 0;
  for (int i = 0; i < n-1; i++) {
    int len1 = expandAroundCenter(s, i, i);
    int len2 = expandAroundCenter(s, i, i + 1);
    int len = max(len1, len2);
    if (len > maxLength) {
      maxLength = len;
      start = i - (len - 1) / 2;
    }
  }
  return s.substr(start, maxLength);
}

2. 我们需要注意一个问题，就是字符串的长度可能是奇数也可能是偶数，因此我们需要分别判断以当前字符为中心的最长回文子串长度是奇数还是偶数。

3. 最后再根据最长回文子串的长度和起始位置，使用substr函数将其截取出来。

三、示例代码

下面是完整的C++实现代码，用于求解一个字符串的最长回文子串：

#include <iostream>
#include <string>
using namespace std;
int expandAroundCenter(string s, int left, int right) {
  int L = left, R = right;
  while (L >= 0 && R < s.size() && s[L] == s[R]) {
    L--;
    R++;
  }
  return R - L - 1;
}
string longestPalindrome(string s) {
  int n = s.size();
  if (n < 2) return s;
  int start = 0, maxLength = 0;
  for (int i = 0; i < n-1; i++) {
    int len1 = expandAroundCenter(s, i, i);
    int len2 = expandAroundCenter(s, i, i + 1);
    int len = max(len1, len2);
    if (len > maxLength) {
      maxLength = len;
      start = i - (len - 1) / 2;
    }
  }
  return s.substr(start, maxLength);
}
int main() {
  string s = "babad";
  string ans = longestPalindrome(s);
  cout << ans << endl;
  return 0;
}

四、总结

本文主要介绍了C++中实现最长回文子串算法的方法，其中涉及到了从中心往外扩展的思想，以及需要注意奇数和偶数长度的情况。通过学习本文，相信大家已经掌握了C++实现最长回文子串算法的方法。

上一篇: idea打包java可执行jar包

下一篇: C++如何获取硬件机器码？

评论区

相似文章