链接：牛客练习赛 17-B 好位置
思路：
题目的意思就是判断串x是不是s的循环子串；可以用KMP来做，KMP模板就不多说了可以翻我之前写的。 1、匹配成功的时候令
j
=
n
e
[
j
]
j=ne[j]
j=ne[j]直至遍历完主串； 2、这里s相当于主串，x为模板串，每匹配成功一次就标记一下（pos[i]标记）匹配成功的那段起点（设为1）和终点（设为-1），最后遍历pos数组求前缀和(sum)来判断是否都是好位置。 判断：
代码：
#include <iostream>
#include <cstring>
using namespace std
;
const int N
= 200000;
char s
[N
], x
[N
];
int ne
[N
], pos
[N
];
int main(){
cin
>> s
+1 >> x
+1;
int ls
= strlen(s
+1);
int lx
= strlen(x
+1);
for(int i
= 2,j
= 0; i
<= lx
; i
++){
while(j
&& x
[i
] != x
[j
+1]) j
= ne
[j
];
if(x
[i
] == x
[j
+1]) j
++;
ne
[i
] = j
;
}
for(int i
= 1,j
= 0; i
<= ls
; i
++){
while(j
&& s
[i
] != x
[j
+1]) j
= ne
[j
];
if(s
[i
] == x
[j
+1]) j
++;
if(j
== lx
){
pos
[i
-lx
+1] = 1;
pos
[i
] = -1;
j
= ne
[j
];
}
}
int sum
= 0;
for(int i
= 1; i
<= ls
; i
++) {
sum
+= pos
[i
];
if (!sum
&& pos
[i
] != -1) {
cout
<< "No" << endl
;
return 0;
}
}
cout
<< "Yes" << endl
;
return 0;
}
Processed:
0.008, SQL:
10
