可在范围 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++ 库函数，使问题变得更容易解决。