题目地址：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"
示例1
输入
8
01112
输出
yes

解题思路：

把1～n转化成对应的2～16进制序列，再在该序列中查找是否存在字符串t

进制转化方法：

1.用int数组存对应的进制序列，再将int数组转化为char[]，分0～9和10～15两中情况转化成对应的字符，获得最终进制序列

2.用string存转化后的最终进制序列，利用string的+操作（int->char的转变）

寻找子串方法：

1.kmp算法

2.如果用的是string存最终进制序列，则可以使用string.find(t)！=string::npos判断存在,时间复杂度为O(n*m)，这种方法在这道题里不会超时。也可以使用kmp，时间复杂度为O(n+m)

ac代码：

string+string.find()

#include <bits/stdc++.h>
#define maxn 5005
#define inf 0x3fffffff
using namespace std;
typedef long long ll;
char to_des(int x)
{

    if(x>=0&&x<=9)
        x=x+'0';
    else if(x>=10&&x<=15)
        x=x-10+'A';
    return (char)x;
}
string num_to_string(int des,int num)
{
    string a;
    while(num>0)
    {
        int x=num%des;
        a=to_des(x)+a;
        num/=des;
    }
    return a;
}
int n;
string t;
int main()
{
    scanf("%d", &n);
    cin >> t;
    bool flag = false;
    for (int i = 2; i <= 16; i++)
    {
        string s;
        for (int j = 1; j <= n; j++)
            s+= num_to_string(i, j);
        if (s.find(t) != string::npos) {
            flag = true;
            break;
        }
    }
    if (flag) printf("yes");
    else printf("no");
    return 0;
}

string+kmp()

#include <bits/stdc++.h>
#define maxn 1000005
#define inf 0x3fffffff
using namespace std;
typedef long long ll;
int Next[maxn];
int n;
string t;
char to_des(int x)
{
    if(x>=0&&x<=9)
        x=x+'0';
    else if(x>=10&&x<=15)
        x=x-10+'A';
    return (char)x;
}
string num_to_string(int des,int num)
{
    string a;
    while(num>0)
    {
        int x=num%des;
        a=to_des(x)+a;
        num/=des;
    }
    return a;
}
void set_Next()
{
    int j=0,k=-1;
    Next[0]=-1;
    while(j<t.length()-1)
    {
        if(k==-1||t[j]==t[k])
        {
            j++;k++;
            Next[j]=k;
        }
        else k=Next[k];
    }
}
int kmp(string s,string t)
{
    int i=0,j=0;
    while(i<s.length() || j<t.length())
    {
        if(j==-1 || s[i]==t[j])
        {
            i++;j++;
        }
        else
            j=Next[j];
        if(j==t.length()) return 1;
    }
    return 0;
}
int main()
{
    scanf("%d", &n);
    cin >> t;
    set_Next();
    bool flag = false;
    for (int i = 2; i <= 16; i++)
    {
        string s;
        for (int j = 1; j <= n; j++)
            s+= num_to_string(i, j);
        if(kmp(s,t))
        {
            flag = true;
            break;
        }
    }
    if (flag) printf("yes");
    else printf("no");
    return 0;
}

int[]+char[]+kmp  来源：https://me.csdn.net/mengxiang000000

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char a[3000050];
char b[1000050];
int nex[3000050];
int lena,lenb;
void set_naxt()//子串的nex数组
{
    int i=0,j=-1;
    nex[0]=-1;
    while(i<lenb)
    {
        if(j==-1||b[i]==b[j])
        {
            i++; j++;
            nex[i]=j;
        }
        else
        j=nex[j];
    }
}
int kmp()
{
    int i=0,j=0;
    set_naxt();
    while(i<lena)
    {
        if(j==-1||a[i]==b[j])
        {
            i++;j++;
        }
        else
        j=nex[j];
        if(j==lenb)
        return 1;
    }
    return 0;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int ans=0;
        scanf("%s",b);
        lenb=strlen(b);
        for(int jinzhi=2;jinzhi<=16;jinzhi++)
        {
            lena=0;
            for(int i=1;i<=n;i++)
            {
                int cnt=0;
                int tmp=i;
                int num[100];
                while(tmp)
                {
                    num[cnt++]=tmp%jinzhi;
                    tmp/=jinzhi;
                }
                for(int j=cnt-1;j>=0;j--)
                {
                    if(num[j]<10)
                    a[lena++]=num[j]+'0';
                    else a[lena++]=num[j]-10+'A';
                }
            }
            ans=max(ans,kmp());
            if(ans>0)break;
        }
        if(ans>0)printf("yes\n");
        else printf("no\n");
    }
}