题目描述

给出一个正整数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 <bits/stdc++.h>
using namespace std;
char s[1000005],t[1000005];
int nex[1000005];
int l;
char f[20];
void la(int n, int b) {
    static char c[16]= {‘0‘,‘1‘,‘2‘,‘3‘,‘4‘,‘5‘,‘6‘,‘7‘,‘8‘,‘9‘,‘A‘,‘B‘,‘C‘,‘D‘,‘E‘,‘F‘};
    l=0;
    while(n) {
        f[l++]=c[n%b];
        n=n/b;
    }
}
void pre(char *p) {
    int i,n,k;
    n=strlen(p);
    nex[1]=nex[0]=0;
    k=0;
    for (i=2; i<=n; i++) {
        for(; k!=0&&p[k]!= p[i-1]; k=nex[k]);
        if(p[k]==p[i-1])k++;
        nex[i]=k;
    }
}
int kmp(char *text, char *p) {
    int m,n,s,q;
    m=strlen(p);
    n=strlen(text);
    q=s=0;
    while (s<n) {
        for (q=nex[q]; q<m&&p[q]==text[s]; q++,s++);
        if (q== 0) s++;
        else if(q==m) {
            return 1;
        }
    }
    return 0;
}
int main() {
    int n;
    scanf("%d",&n);
    getchar();
    for(int i=0; ; i++) {
        char c=getchar();
        if(c==‘\n‘) {
            t[i]=0;
            break;
        }
        t[i]=c;
    }
    pre(t);
    for(int j=16; j>1; j--) {
        int b=0;
        for(int i=1; i<=n; i++) {
            la(i,j);
            for(int k=l-1; k>=0; k--)
                s[b++]=f[k];
        }
        s[b]=0;
        if(kmp(s,t))
            return 0*puts("yes");
    }
    return 0*puts("no");
}