链接
点击跳转
题解
要看
a
a
a串是不是
b
b
b串的子串，就把
a
a
a串拼在
b
b
b串后面，中间加一个分隔符
然后跑一下
k
m
p
kmp
kmp，看一下是否有某个前缀的
n
e
x
t
next
next等于串长
会不会大于串长呢？不会，因为有分隔符
代码
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 5000010
#define maxe 5000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(i=a;i<=b;i++)
#define drep(i,a,b) for(i=a;i>=b;i--)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std
;
using namespace __gnu_pbds
;
typedef long long ll
;
typedef pair
<int,int> pii
;
typedef pair
<ll
,ll
> pll
;
ll
read(ll x
=0)
{
ll c
, f(1);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-0x30;
return f
*x
;
}
struct KMP
{
int n
, next
[maxn
], t
[maxn
];
void clear()
{
cl(next
), n
=0;
}
void build(const char *r
, int len
)
{
int i
, j
=0;
n
=len
;
for(i
=1;i
<=len
;i
++)t
[i
]=r
[i
]; t
[len
+1]=0;
for(i
=2;i
<=len
;i
++)
{
for(;j
and t
[j
+1]!=t
[i
];j
=next
[j
]);
next
[i
] = t
[j
+1]==t
[i
]?++j
:0;
}
}
int move(int pos
, int x
)
{
for(;pos
and t
[pos
+1]!=x
;pos
=next
[pos
]);
return t
[pos
+1]==x
? pos
+1 : 0;
}
}kmp
;
char toDig(int x
)
{
if(x
<10)return 0x30+x
;
return 'A'+x
-10;
}
string
toNum(int x
, int k
)
{
string ret
;
while(x
)
{
ret
+= toDig(x
%k
);
x
/=k
;
}
reverse(ret
.begin(),ret
.end());
return ret
;
}
string
s(int n
, int k
)
{
string ret
;
int i
;
rep(i
,1,n
)ret
+= toNum(i
,k
);
return ret
;
}
bool check(int n
, int k
, string t
)
{
int l
= t
.length(), i
;
t
+= '|';
t
+= s(n
,k
);
kmp
.build(t
.c_str()-1,t
.length());
rep(i
,l
+1,kmp
.n
)if(kmp
.next
[i
]==l
)return true;
return false;
}
int main()
{
int n
, i
;
string t
;
ios
::sync_with_stdio(false);
cin
>>n
>>t
;
rep(i
,2,16)if(check(n
,i
,t
))
{
printf("yes");
return 0;
}
printf("no");
return 0;
}
