C++ 从无限字符串的前N个字符中找到只有4的最长子字符串

在这个教程中，我们实现了一种方法来找到只包含4的最长子字符串，使用无限字符串的前N个字符。无限字符串使用4的样式如下：”44444444……”，我们定义该字符串的字符长度来解决问题。为了解决这个教程问题，考虑一个输入的数字字符串，我们使用两个条件来解决这个问题，这两个条件如下：

考虑一个包含随机数字的输入字符串，并生成该字符串中只有4的最长子字符串。
我们考虑一个由4、5、44、45等组合形成的无限字符串。这个字符串将以递增顺序包含4和5的组合数字。使用这个字符串找到只包含4的最长子字符串的长度。

示例1

String = “3444445443”

输出

the longest substring containing 4’s is 44444

说明

在上面的输入字符串444445443中，有3个4。任务是生成一个只包含4的子字符串。所以使用输入字符串的任务输出是44444。

示例2

在这个演示中，我们采用递增顺序的4和5位数字组合的输入字符串。我们定义输入字符串的长度，并生成以只包含4的最长子字符串长度形式的输出。

Total characters in the string = 6

输出

说明

我们将输入字符串取6个字符，并且得到的输入字符串是454445。使用这个字符串，使用前N个字符中只包含4个字符的子字符串的长度为3。

演示3

Length of the string = 8

输出

输入字符串的长度为8，因此可能的输入字符串是45444554。使用初始字符仅包含4的子字符串的长度为3。

C++库函数

语法

length()： 这是一个字符串类库函数，返回字符串的长度。字符串的字节格式长度是字符串中所有字符的总和。

string_name.length();

substr()： 它在字符串类头文件中定义。使用输入的字符串生成子字符串。它接受2个参数：开始位置和长度。

string_name.substr(begin, length);

步骤1

获取输入字符串的长度。
函数 maxlengthSubstr() 返回包含只有4的最长子字符串的长度。
初始化一个前缀数组以生成可能的输入字符串组合数。
数组将从数组变量迭代到 MAXN。
通过计算 result 变量的值来找到子字符串的长度。

示例1

在这个实现中，用户自定义函数 maxLengthSubstr() 返回包含只有4的最长子字符串的长度。初始化 pre_arr{} 来计算长度。不需要完整生成输入字符串，而是指定其长度。代码开始时定义了一个常量变量 MAXN。

其 C++ 实现如下：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 30

// Function returning the length of the longest substring containing only 4
int maxLengthSubstr(int Num)
{
    //variable containing the result
    int ans;

    // Initialize array to make groups
    int pre_arr[MAXN], q = 1;

    pre_arr[0] = 0;
    for (int x = 1; x < MAXN; x++)
    {
        q *= 2;
        pre_arr[x] = pre_arr[x - 1] + x * q;
    }

    int l;

 //Finding the length of the longest substring
    for (int x = 1; x < MAXN; x++) 
    {
        if (pre_arr[x] >= Num) 
        {
            l = x;
            break;
        }
    }

    int i = Num - pre_arr[l - 1];
    int j = 2 * l - 1;

    if (i >= j)
        ans = min(i, j);
    else
        ans = max(i, 2 * (l - 2) + 1);

    return ans;
}

// Controller
int main()
{
    int Num = 8;
    cout << "Maximum length of the longest substring of 8 string characters containing only 4s is : " << maxLengthSubstr(Num);

    return 0;
}

输出

Maximum length of the longest substring of 8 string characters containing only 4s is : 3

示例2

在这个实现中，用户定义的函数longestSubstr()返回包含输入字符串的前N个字符中只包含4的最长子串。将输入字符串的每个字符与4进行比较，当匹配时，增加计数变量的值。

下面是以上解释的C++实现。

#include <iostream>
#include <string>
using namespace std;

//function returning the longest substring containing only 4
string longestSubstring(const string& str) 
{
    int maxLen = 0;
    int start = 0;
    int currentLen = 0;
    int currentStartIndex = 0;

//iterating characters of the string
    for (int x = 0; x < str.length(); x++) 
    {
        if (str[x] == '4') 
        {
            if (currentLen == 0) 
            {
                currentStartIndex = x;
                currentLen = 1;
            }
            else 
            {
                currentLen++;
            }

            if (currentLen > maxLen) 
            {
                maxLen = currentLen;
                start = currentStartIndex;
            }
        } 
        else 
        {
            currentLen = 0;
        }
    }

    string longestSubstr = str.substr(start, maxLen);
    return longestSubstr;
}

//Controller
int main() 
{
    string str = "344444405474444";

    string longestSubstr = longestSubstring(str);
    cout << "Longest substring of only 4's: " << longestSubstr << endl;

    return 0;
}

输出

Longest substring of only 4's: 44444

结论

我们已经找到了从输入字符串的前N个字符中找到只包含 4的最长子字符串的结束。这是使用C++逻辑完成的。第一个解决方案涉及比较输入字符串中的每个字符以找到只有4的最长子字符串。在第二个解决方案中，确定包含只有4的最长子字符串的长度。这是通过使用一个包含递增顺序的数字4和5的字符串来实现的，如4, 5, 44, 45 ….

这两个解决方案都使用了一些C ++库函数来解决问题。使用一些示范来阐述问题陈述的目的。