题解 | #子串#

思路

被这道题坑了，看完题意秒写Kmp，交了之后只过了90%，各种改最后才发现没有考虑ABCDEF的情况。（啊太粗心了）
做法：第一层循环是进制数k，递归或者循环+reverse得出字符串s，然后如果kmp得t是s的子串，则直接输出yes结束程序，如果k到16还是没有退出，那么输出no。怕麻烦不想写kmp也可以用s.find(t)!=0。

代码

#include<bits/stdc++.h>
using namespace std;

int n,kmp[1000005];
string t,s;

string work(int x,int y){
    string str="";
    while(x){
        if(x%y>=10) str+=x%y+'A'-10;
        else str+=x%y+'0';
        x/=y;
    }
    reverse(str.begin(),str.end());
    return str;
}

void kmp_pre(string str){
    int j=0;
    kmp[0]=0;
    for(int i=1;i<str.length();i++){
        j=kmp[i];
        while(j&&str[j]!=str[i]) j=kmp[j];
        if(str[i]==str[j]) kmp[i+1]=j+1;
        else kmp[i+1]=0;
    }
}


int main(){
    scanf("%d",&n);
    cin>>t;
    kmp_pre(t);
    //for(int i=0;i<=t.length();i++) cout<<kmp[i]<<" ";
    for(int k=2;k<=16;k++){
        s="";
        for(int i=1;i<=n;i++) s+=work(i,k);
        int j=0;
        for(int i=0;i<s.length();i++){
            while(j&&s[i]!=t[j]) j=kmp[j];
            if(s[i]==t[j]){
                j++;
                if(j==t.length()){
                    cout<<"yes"<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"no"<<endl;
    return 0;
}