k进制的子字符串问题

Question

定义str(n.k)为将k进制下的0到n拼接起来的字符串
例如str(12，12)=0123456789ab10,str(10,2)=011011100101110111100010011010。
现在对于给定的n和字符串s，判断s是否为k(2 s k s 16)进制下str(n,k)的子串。
输入
第一行一个整数n(1 s n s50,000)。
第二行一个字符串t(长度 s 1,000,000)
输出
"yes"表示存在满足条件的k，否则输出“no"
样例输入
8
01112
样例输出
yes

Answer 1

该回答引用GPTᴼᴾᴱᴺᴬᴵ
这道题可以通过枚举k的值，将str(n,k)转换为10进制，然后判断给定的字符串s是否是这个10进制数的子串来解决。

具体来说，我们可以从2到16枚举k，对于每一个k，将str(n,k)转换为10进制数，然后判断字符串s是否是这个10进制数的子串即可。

转换为10进制数的方法是将str(n,k)中每个字符转换为对应的数字，然后将它们乘以k的不同幂次，最后相加即可。

代码如下：

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

using namespace std;

// 将一个k进制数转换为10进制数
int toDecimal(string s, int k) {
    int decimal = 0;
    for (int i = 0; i < s.size(); i++) {
        decimal = decimal * k + s[i] - '0';
    }
    return decimal;
}

int main() {
    int n;
    string s;
    cin >> n >> s;

    bool flag = false; // 标记是否存在满足条件的k
    for (int k = 2; k <= 16; k++) {
        string str_n_k = "";
        for (int i = 0; i <= n; i++) {
            int num = i;
            string s_num = "";
            while (num > 0) {
                int mod = num % k;
                s_num += to_string(mod);
                num /= k;
            }
            reverse(s_num.begin(), s_num.end());
            str_n_k += s_num;
        }

        int decimal = toDecimal(str_n_k, k);
        string s_decimal = to_string(decimal);
        if (s_decimal.find(s) != string::npos) {
            flag = true;
            break;
        }
    }

    if (flag) {
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }

    return 0;
}

时间复杂度为O(nlogn)。