c++ 最长回文字串
时间: 2024-08-17 16:03:35 浏览: 45
在C++中,寻找最长回文子串通常是一个经典的问题,可以采用动态规划(Dynamic Programming)的方法来解决。有一种常见的算法叫做Manacher's Algorithm,它的时间复杂度是O(n),空间复杂度也是O(n)。这个算法通过维护一个回文半径数组,可以在遍历字符串的同时找到每个位置为中心的最长回文子串。
基本步骤包括:
1. 初始化两个变量,中心点`center`和最右边界`right`,以及一个回文半径数组`P[]`,其中`P[0] = P[1] = 0`。
2. 遍历字符串,对于每个字符`c`:
- 如果`c`位于`right`的左边,那么其回文半径可以从已知的较小半径开始计算,即`P[i] = min(right-i, P[2*center-i])`。
- 否则,从`c`开始向两边扩展,尝试更新`right`和`P[]`。
- 更新最长回文子串的信息,如果`P[i]`扩展到了`right`,则更新`center`和`right`的位置。
3. 返回`P[]`中的最大值对应的回文串长度,再根据该长度和原字符串返回最长的回文子串。
相关问题
c++ 最长回文字串代码
在 C++ 中,寻找最长回文子串的问题通常采用动态规划(Dynamic Programming)的方法解决。下面是一个简单的 C++ 代码示例,使用了 Manacher's Algorithm 进行优化,它的时间复杂度为 O(n):
```cpp
#include <iostream>
#include <string>
class Solution {
public:
std::string longestPalindrome(std::string s) {
if (s.empty()) return "";
int n = s.size();
std::string t = '#'; // 添加特殊字符,便于处理边界情况
for (char ch : s) {
t += ch;
}
t += '#';
int P = 0, center = 0, maxLen = 1; // P记录已知回文中心,center记录当前回文半径
for (int i = 1; i < n + 1; ++i) {
int mirror = 2 * center - i; // 根据对称原理计算i位置的回文镜像
if (i < P) {
int len = std::min(P - i, maxLen);
if (t[i - len] == t[mirror + len]) { // 如果左右两边字符相等
maxLen = len + 2; // 更新maxLen
} else {
maxLen = 1; // 否则恢复到1
}
}
while (i - maxLen >= 0 && i + maxLen < n && t[i - maxLen] == t[i + maxLen]) { // 检查并向两边扩展
maxLen++;
}
if (i + maxLen > P) {
P = i + maxLen;
center = i;
}
}
// 返回最长回文子串
return s.substr(s.size() / 2 - maxLen / 2, maxLen);
}
};
int main() {
Solution solution;
std::string str = "babad";
std::cout << "Longest palindrome substring is: " << solution.longestPalindrome(str) << std::endl;
return 0;
}
```
这个代码首先将原字符串 `s` 增加了特殊字符以便处理奇数长度的回文,然后通过动态维护已知的最大回文半径和回文中心,找到最长的回文子串。
用c++编写一个程序:从输入的一行字符串中求出最长英文单词长度及最长单词个数,并输出长度和个数
```c
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main() {
char str[1000];
int len = 0, cnt = 0, max_len = 0, max_cnt = 0;
fgets(str, 1000, stdin); // 从标准输入读入一行字符串
for (int i = 0; i < strlen(str); i++) {
if (isalpha(str[i])) { // 如果是字母
len++; // 单词长度加1
} else { // 如果不是字母,说明一个单词结束
if (len > 0) { // 如果单词长度大于0
cnt++; // 单词个数加1
if (len > max_len) { // 如果当前单词长度大于最长单词长度
max_len = len; // 更新最长单词长度
max_cnt = 1; // 最长单词个数为1
} else if (len == max_len) { // 如果当前单词长度等于最长单词长度
max_cnt++; // 最长单词个数加1
}
len = 0; // 重置单词长度
}
}
}
printf("最长英文单词长度为:%d,最长单词个数为:%d\n", max_len, max_cnt);
return 0;
}
```
注:该程序假设一个单词中只包含英文字母。
阅读全文