子串

题意：一个正整数n，字符串 s(n,k) 为1-n在k进制下的相连组成的字符串，2 <= k <= 16。给你一个字符串t，判断是否存在k使得t为s(n,k)的子串。
输入：
第1行，一个正整数，n，1 <= n <= 50000；
第2行，一个字符串t，长度<= 1000000；
输出：
一行，yes或者no。
算法标签：**模式匹配，kmp
解法：**
kmp模板：
1.一个next数组：
void getnext()
{
int i=0,j=-1;
ne[0]=j;
while(i {
if(j==-1||mo[i]==mo[j])
ne[++i]=++j;
else
j=ne[j];
}
}
2.kmp模式匹配算法
bool kmp()
{
int i=0,j=0;
while(i {
if(j==-1||mo[j]==str[i])
{
i++;
j++;
}
else
j=ne[j];
if(j>=n2)
{
return true;
}
}
return false;
}

AC代码：
#include
using namespace std;
const int N = 1e6+5;
char str[N],mo[N],ts[N];
int ne[N];
int n1,n2;
void getnext()
{
int i=0,j=-1;
ne[0]=j;
while(i {
if(j==-1||mo[i]==mo[j])
ne[++i]=++j;
else
j=ne[j];
}
}
bool kmp()
{
int i=0,j=0;
while(i {
if(j==-1||mo[j]==str[i])
{
i++;
j++;
}
else
j=ne[j];
if(j>=n2)
{
return true;
}
}
return false;
}
int main ()
{
int n;
cin>>n>>mo;
n2=strlen(mo);
getnext();
int f=0;
for (int i=2;i<=16;i++)
{
int d=-1;
for (int j=1;j<=n;j++)
{
int x=j,y=0;
while(x)
{
ts[++y]=x%i+’0’;
if(ts[y]>’9’)
ts[y]=’A’+ts[y]-‘9’-1;
x/=i;
}
for (int g=y;g>=1;g—)
str[++d]=ts[g];
}
n1=d+1;
if(n1 if(kmp())
{
f=1;
break;
}
}
if(f)
cout<<”yes”;
else
cout<<”no”;
return 0;
}