题解 | #子串#

链接：https://ac.nowcoder.com/acm/problem/13253 来源：牛客网

题目描述 给出一个正整数n，我们把1..n在k进制下的表示连起来记为s(n,k)，例如s(16,16)=123456789ABCDEF10, s(5,2)=11011100101。现在对于给定的n和字符串t，我们想知道是否存在一个k(2 ≤ k ≤ 16)，使得t是s(n,k)的子串。

输入描述: 第一行一个整数n(1 ≤ n ≤ 50,000)。 第二行一个字符串t(长度 ≤ 1,000,000)。

输出描述: "yes"表示存在满足条件的k，否则输出"no"

示例 输入： 8 01112 输出： yes

#include<cstring>
#include<algorithm>

using namespace std;

int n;
string t,s;

int main()
{
    cin >> n >> t;
    int z = 0;
    string m = "0123456789ABCDEF";
    for(int i = 2 ; i <= 16 ; i ++)
    {
        s = "";
        for(int j = n ; j >= 1 ; j --)
        {
            int d = j;
            while(d != 0){s.push_back(m[d%i]);d /= i;}
        }
        reverse(s.begin(),s.end());
        if(s.find(t) != -1) {cout << "yes" << endl;z = 1;break;}
    }
    if(z == 0) cout << "no" << endl;
    return 0;
}