C++回文实现方法介绍("C++实现回文检测的详细方法解析")

原创

ithorizon 6个月前 (10-20) 阅读数 35 #后端开发

C++实现回文检测的详细方法解析

一、回文的概念

回文是指一个字符串（或数字）正着读和反着读都相同的词语或短语。例如，“上海自来水来自海上”和“12321”都是回文。

二、C++实现回文检测的必要性

在编程中，回文检测可以用于解决一些特定问题，如字符串处理、算法竞赛、密码学等领域。通过实现回文检测，我们可以锻炼自己的编程技巧，节约代码逻辑思维能力。

三、C++实现回文检测的详细方法

下面我们将介绍几种常见的C++实现回文检测的方法。

1. 方法一：双指针法

双指针法是最直观的回文检测方法，其基本思想是：使用两个指针分别指向字符串的起始和终结，然后逐个比较指针所指的字符，如果相同则继续，如果不同则不是回文。


#include 
#include 
#include 
bool isPalindrome1(const std::string &str) {
    int left = 0;
    int right = str.size() - 1;
    while (left < right) {
        if (str[left] != str[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
int main() {
    std::string str = "上海自来水来自海上";
    std::cout << "字符串 \"" << str << "\" 是否为回文："
              << (isPalindrome1(str) ? "是" : "否") << std::endl;
    return 0;
}

2. 方法二：字符串翻转法

字符串翻转法是将原字符串翻转后与原字符串进行比较，如果相同则是回文。这种方法虽然单纯，但需要额外的空间来存储翻转后的字符串。


#include 
#include 
#include 
bool isPalindrome2(const std::string &str) {
    std::string reversedStr = str;
    std::reverse(reversedStr.begin(), reversedStr.end());
    return str == reversedStr;
}
int main() {
    std::string str = "上海自来水来自海上";
    std::cout << "字符串 \"" << str << "\" 是否为回文："
              << (isPalindrome2(str) ? "是" : "否") << std::endl;
    return 0;
}

3. 方法三：中心扩展法

中心扩展法是从字符串的中间起始，向两边扩展，比较两边的字符是否相同。这种方法适用于字符串长度为奇数和偶数的情况。


#include 
#include 
bool isPalindrome3(const std::string &str) {
    int left = str.size() / 2 - 1;
    int right = str.size() / 2;
    while (left >= 0 && right < str.size()) {
        if (str[left] != str[right]) {
            return false;
        }
        left--;
        right++;
    }
    return true;
}
int main() {
    std::string str = "上海自来水来自海上";
    std::cout << "字符串 \"" << str << "\" 是否为回文："
              << (isPalindrome3(str) ? "是" : "否") << std::endl;
    return 0;
}

4. 方法四：Manacher算法

Manacher算法是一种高效的回文检测算法，它利用回文的对称性质，通过预处理和中心扩展，避免重复比较，从而节约检测高效。


#include 
#include 
#include 
std::string preprocess(const std::string &str) {
    std::string processedStr = "#";
    for (char ch : str) {
        processedStr += ch;
        processedStr += '#';
    }
    return processedStr;
}
std::vector manacher(const std::string &str) {
    std::string processedStr = preprocess(str);
    std::vector p(processedStr.size(), 0);
    int center = 0;
    int right = 0;
    for (int i = 1; i < processedStr.size(); i++) {
        int mirror = 2 * center - i;
        if (i < right) {
            p[i] = std::min(right - i, p[mirror]);
        }
        while (processedStr[i + (1 + p[i])] == processedStr[i - (1 + p[i])]) {
            p[i]++;
        }
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }
    return p;
}
bool isPalindrome4(const std::string &str) {
    std::vector p = manacher(str);
    int maxLen = 0;
    for (int len : p) {
        maxLen = std::max(maxLen, len);
    }
    return maxLen >= str.size();
}
int main() {
    std::string str = "上海自来水来自海上";
    std::cout << "字符串 \"" << str << "\" 是否为回文："
              << (isPalindrome4(str) ? "是" : "否") << std::endl;
    return 0;
}