C++ 找出字符串中的最小子字符串使其均为5的幂次方

在本教程中，我们使用C++实现两个示例来找出给定字符串中的最小子字符串数量。这些子字符串都是5的幂次方，也就是说，这些子字符串是5的因子。要实现这个示例，需要输入一个二进制字符串，并生成可能的最小子字符串，这些子字符串都是5的因子。如果你想知道一个子字符串是否是5的幂次方，请检查它的十进制值。

二进制字符串由1和0组成，我们无法找到一个特定的二进制字符串，它是5的倍数还是不是。例如，0101的十进制值是5。

演示1

String = “101101”

输出

使用上述输入字符串，可能是5的幂的子字符串的数量是2。可能的子字符串是“101”和“101”（子字符串可以是任何一个）。这些子字符串是5的幂。101的十进制值是5，可以被5整除。

演示2

String = “1111111

输出

在上面的例子中，使用上述输入字符串，有2个可能的子字符串是5的幂，分别是1111和11111111。1111的十进制值等于15，11111111的十进制值等于225，这两个十进制值都是5的因子或5的幂。

步骤

以二进制形式获取输入字符串。
使用length()函数找到字符串的长度。
使用输入字符串生成可能的子字符串。
检查生成的子字符串是否是5的因子。
如果子字符串是5的幂，则将值保存在计数器变量中。
打印计数器变量的值。

语法

在下面的示例中，使用了以下C++库函数：

length()： 这是一个内置的字符串库函数。它以字节形式返回输入字符串的长度。长度定义了字符串中的字符数。

string_name.length();

memset()函数： 它将连续的内存块赋值给指定的值。它有3个参数：字符、长度和一个整数值。

memset(char, len, int);

unordered_set() : unordered_set()是一种无序的数据结构，允许按照无序的方式进行插入和删除操作。

unordered_set(data_type) set_name;

unordered_set.insert(): 这是unordered_set头文件的库函数。它向unordered set中插入元素。

unordered_set_name.insert(value);

unordered_set.find() : 它用于查找unordered_set中存储的值。它在unordered_set头文件中定义。

unordered_set_name.find(value);

substr()： 是一个字符串类库函数，用于使用输入字符串生成子字符串。它接受两个参数，分别定义了它的起始点和子字符串的长度。

string_name.substr(pos, len);

stoi()函数： 这是标准的字符串类库函数，用于将字符串转换为整数。在C++编程中经常使用。stoi()代表字符串转换为整数值。

stoi(string str, position, base);

vector : 它是一个动态数组。此外，它为其元素提供了连续的内存位置。

vector<data_type> vector_name;

示例1

通过定义一个 long long 类型的头文件，我们实现了一个示例。输入一个字符串，生成子字符串并检查这些子字符串是否为5的幂因子。打印可以使用输入字符串生成的最小子字符串数量。

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long

//function to check substring is power of 5
bool ispowerOfFive(ll len)
{
    if (len < 125)
        return (len == 1 || len == 5 || len == 25);
    if (len % 125 != 0)
        return false;
    else
        return ispowerOfFive(len / 125);
}

//function to return decimal value 
ll decimalValue(string str, int x, int y)
{
    ll result = 0;
    for (int i = x; i < y; i++) 
    {
        result = result * 2 + (str[i] - '0');
    }
    return result;
}

int minCutValue(string str, int len)
{
    int dpg[len + 1];

    // memory allocation using memset
    memset(dpg, len + 1, sizeof(dpg));
    dpg[0] = 0;

    for (int x = 1; x <= len; x++) 
    {

        if (str[x - 1] == '0')
            continue;
        for (int y = 0; y < x; y++) 
        {

            if (str[y] == '0')
                continue;

            ll value = decimalValue(str, y, x);
 // calling function
            if (!ispowerOfFive(value))
                continue;

            dpg[x] = min(dpg[x], dpg[y] + 1);
        }
    }

    return ((dpg[len] < len + 1) ? dpg[len] : -1);
}

 int main()
{
    string str = "1011011011";
    int len = str.length();
    cout << minCutValue(str, len);

    return 0;
}

输出

示例2

我们通过使用一些用户自定义函数来实现一个例子。使用向量（类似于没有预定义尺寸的数组）和动态规划方法来生成使用输入字符串的子字符串。在使用substr()函数生成子字符串后，检查它们是否是5的幂。

#include <vector>
#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
using namespace std;

bool isPower(int n) 
{
    while (n % 5 == 0)
    {
        n /= 5;
    }
    return n == 1;
}

int countSubstr(const string& s) 
{
    int l = s.length();
    unordered_set<int> powersOfFive;

    // Pre-compute powers of 5 up to the maximum length of substring possible
    for (int x = 0; x < l; x++) 
    {
        int pwr = 1;
        for (int y = 0; y <= x; y++)
        {
            pwr *= 5;
        }
        powersOfFive.insert(pwr);
    }

    // Dynamic programming approach to count minimum substrings
    vector<int> dpg(l + 1, l + 1);
    dpg[0] = 0;

    for (int x = 1; x <= l; x++) 
    {
        for (int y = 0; y < x; y++) 
        {
            string sb = s.substr(y, x - y);
            int sbNum = stoi(sb, nullptr, 2);  // Parse binary string as integer

            if (powersOfFive.find(sbNum) != powersOfFive.end()) 
            {
                dpg[x] = min(dpg[x], dpg[y] + 1);
            }
        }
    }

    return dpg[l] == l + 1 ? -1 : dpg[l];
}

int main() {
    string s = "1111101";

    int output = countSubstr(s);
    if (output == -1) 
    {
        cout << "No valid substrings found." << endl;
    }
    else 
    {
        cout << "Minimum number of substrings: " << output << endl;
    }

    return 0;
}