C++での回文（パリンドローム）テクニック

回文とは、前から読んでも後ろから読んでも同じ並びになる文字列のことです。ここでは、回文に関する様々なテクニックをC++のコード例を用いて解説します。

1. 文字列の反転による判定

最も単純なアプローチは、文字列を反転させて元の文字列と比較することです。

#include <iostream>
#include <string>
#include <algorithm>

bool isPalindromeReverse(const std::string& s) {
    std::string reversed = s;
    std::reverse(reversed.begin(), reversed.end());
    return s == reversed;
}

int main() {
    std::string str = "racecar";
    std::cout << str << " is palindrome: " << (isPalindromeReverse(str) ? "Yes" : "No") << std::endl;
    return 0;
}

このアプローチは簡単ですが、追加のメモリを使用し、文字列全体を反転させる必要があります。

2. 2つのポインタを使用した判定

より効率的なアプローチは、2つのポインタを使用することです。

bool isPalindromeTwoPointers(const std::string& s) {
    int left = 0;
    int right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

このアプローチは追加のメモリを使用せず、必要に応じて早期に終了できます。

3. 回文の数を数える

回文の数を数える問題では、中央から外側に向かって拡張していくテクニックがよく使用されます。

int countPalindromes(const std::string& s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        // 奇数長の回文
        count += expandAroundCenter(s, i, i);
        // 偶数長の回文
        count += expandAroundCenter(s, i, i + 1);
    }
    return count;
}

int expandAroundCenter(const std::string& s, int left, int right) {
    int count = 0;
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        count++;
        left--;
        right++;
    }
    return count;
}

このアプローチは、奇数長と偶数長の両方の回文を考慮しています。

4. 最長回文部分文字列

最長回文部分文字列を見つける問題も、中央から拡張するテクニックを使用します。

std::string longestPalindromicSubstring(const std::string& s) {
    if (s.empty()) return "";
    int start = 0, maxLength = 1;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = std::max(len1, len2);
        if (len > maxLength) {
            start = i - (len - 1) / 2;
            maxLength = len;
        }
    }
    return s.substr(start, maxLength);
}

int expandAroundCenter(const std::string& s, int left, int right) {
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

このアプローチは、各文字（奇数長）と各文字ペア（偶数長）を中心として拡張し、最長の回文を見つけます。

5. 回文部分列（動的計画法）

回文部分列の問題は、重複する部分問題があるため、動的計画法を使用します。

int longestPalindromicSubsequence(const std::string& s) {
    int n = s.length();
    std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
    
    // すべての1文字は長さ1の回文
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    
    // 長さ2以上の部分列を埋める
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && len == 2) {
                dp[i][j] = 2;
            }
            else if (s[i] == s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            }
            else {
                dp[i][j] = std::max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    
    return dp[0][n-1];
}

この動的計画法のアプローチは、部分問題の結果を保存し再利用することで効率的に解を求めます。

まとめ

文字列の反転: 簡単だが追加のメモリを使用
2つのポインタ: 効率的で追加のメモリを使用しない
回文の数を数える: 中央から拡張するテクニックを使用
最長回文部分文字列: 中央から拡張するテクニックを使用
回文部分列: 動的計画法を使用

これらのテクニックを適切に選択し適用することで、様々な回文関連の問題を効率的に解決することができます。問題の特性（部分文字列 vs 部分列、カウント vs 最長など）に応じて、最適なアプローチを選択することが重要です。

Palindrome - tanakakenji/Rinko GitHub Wiki

C++での回文（パリンドローム）テクニック

1. 文字列の反転による判定

2. 2つのポインタを使用した判定

3. 回文の数を数える

4. 最長回文部分文字列

5. 回文部分列（動的計画法）

まとめ

⚠️ GitHub.com Fallback ⚠️

Palindrome - tanakakenji/Rinko GitHub Wiki

C++での回文（パリンドローム）テクニック

1. 文字列の反転による判定

2. 2つのポインタを使用した判定

3. 回文の数を数える

4. 最長回文部分文字列

5. 回文部分列（動的計画法）

まとめ

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️