可在範圍 L 和 R 內的字元建立的最大長度迴文子串

---

簡介

迴文是指正讀和反讀都一樣的字串。例如，“Mam”就是一個迴文字串。在本教程中，我們將使用 C++ 程式設計來找到透過預定義字元範圍建立的最大長度迴文子串。

我們的任務是使用輸入字串找到最大長度的迴文子串。我們定義字元的範圍來生成該字串。根據情況，L 和 R 可以持有任何值。

演示 1

String = “amem”
Range = {1,4}

輸出

3

在以上演示中，輸入字串為“amem”，生成迴文子串的範圍為 {1, 4}。此範圍定義了迴文子串的字元起始值和結束值。使用此範圍，最大長度的迴文子串為 3，這些字串為 mem 或 mam。

演示 2

String = “bbbb”
Range = {1, 4}

輸出

4

在以上輸入字串中，在定義的範圍內最長的迴文子串長度為 4。該回文子串為 bbbb。

示例中使用的 C++ 庫函式

語法

memset() : 此標準庫函式在 <cstring> 標頭檔案中定義。它將記憶體塊設定為特定值。它複製值。它接受 3 個引數：ptr、val 和 num。ptr 是起始地址指標，val 是要設定的值，num 是要設定的數量。

memset(ptr, val, num);

size() : 此庫函式在 <std> 標頭檔案中定義。它返回字串的大小。

string_name.size();

Vector: 此庫函式在 <vector> 標頭檔案中定義。它是 C++ 中的動態陣列。在向此陣列新增或刪除元素時，它會調整自身大小。

vector<data_type> vector_name; 

演算法

• 獲取輸入字串。

• 使用計數器變數計算範圍內字元的頻率。

• 找到奇數和偶數頻率。

• 最長迴文子串的長度是奇數頻率減 1 與偶數頻率的總和。

• 列印結果。

示例 1

我們使用 C++ 程式語言實現了其中一個演示。使用者定義的函式計算奇數和偶數頻率。將偶數和奇數減 1 的頻率相加，以計算定義範圍內迴文子串的最大長度。

#include <bits/stdc++.h>
using namespace std;
#define N 4
 
//user-defined function to calculate frequencies
int calculateQueries(int m, int s, int p[N][26])
{
    m--;
    s--;
 
    // marking for odd frequency
    bool f = false;
 
    // counter variable to count the maximum length
    int cnt = 0;
 
    // Traversing all characters
    for (int x = 0; x < 26; x++) 
    {
        int cnt1 = p[s][x];
        if (m > 0)
            cnt1 -= p[m - 1][x];
 
        // finding odd frequencies
        if (cnt1 % 2 == 1) 
        {
            f = true;
            cnt += cnt1 - 1;
        }
     
        else
            cnt += cnt1;
    }
 
    if (f)
        cnt += 1;
 
    return cnt;
}
 
void calculateFreq(string str, int p[N][26])
{
    int m = str.size();
 
    // Iteration for counter variable
    for (int x = 0; x < m; x++)
    {
        p[x][str[x] - 'a']++;
    }
 
    for (int x = 1; x < m; x++)
    {
        for (int y = 0; y < 26; y++)
            p[x][y] += p[x - 1][y];
    }
}
 
// Code controller
int main()
{
    string str = "bbbbb";
 
    // prefix array
    int p[N][26];
    memset(p, 0, sizeof p);
    calculateFreq(str, p);
 
    int q[][2] = { 1, 4};
    int sq = sizeof(q) / sizeof(q[0]);

    for (int x = 0; x < sq; x++)
    {
        cout << calculateQueries(q[x][0],
                               q[x][1], p)
             << endl;
    }
 
    return 0;
}

輸出

4

示例 2

我們使用 C++ 程式設計概念實現了演示。使用向量計算迴文字元的頻率。建立一個使用者定義的函式 maxLengthPalindrome() 以查詢 {1, 4} 內所需的迴文子串長度。

您可以根據需要更改輸入字串和範圍。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxLengthPalindrome(string& s, int st, int e) 
{
    // Initialize a vector to store the frequency of each character
    vector<int> freq(26, 0);

    // Count the frequency of characters within the given range
    for (int x = st - 1; x <= e - 1; x++)
    {
        freq[s[x] - 'a']++;
    }

    int l = 0;
    bool oddFreq = false;

    // Calculate the maximum length palindrome
    for (int x = 0; x < 26; x++)
    {
        l += freq[x] / 2 * 2;
        
        if (freq[x] % 2 == 1) 
        {
            oddFreq = true;
        }
    }

    // If there is a character with an odd frequency, increment the length by 1
    if (oddFreq) 
    {
        l++;
    }

    return l;
}

int main() 
{
    string s = "amem";
    int st = 1;
    int e = 4;

    int maxLen = maxLengthPalindrome(s, st, e);

    cout << "Maximum length palindrome: " << maxLen << endl;

    return 0;
}

輸出

Maximum length palindrome: 3

結論

我們完成了本教程，學習如何在給定範圍內找到最大長度的迴文子串。我們實現了兩個不同的示例來解決此任務。這些演示幫助我們理解了問題陳述的要求。我們定義了範圍，以使用輸入字串生成最大長度的迴文子串。C++ 實現使用了不同的 C++ 庫函式，使問題變得更容易解決。