cbecbcdebadeaecadcbdbeccdaeaeadcedcdeaadeadebaeaddcaabbdceeadcbaecdeabeccacaeeedaaebaaabbecaebeeadac
<999924 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#20659 | #1057. 一姬的BM算法 | Accepted | 100 | 1110 ms | 4776 K | C++ 11 / 1.3 K | JM233333 | 2019-07-29 19:32:23 |
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
void make_fail(char* mode);
bool kmp(char* str, char* mode);
const int MAX = 1e6 + 5, MAXN = 2 * MAX;
char A[MAXN], B[MAX];
int fail[MAXN];
int main() {
// freopen("test.txt", "r", stdin);
while (scanf("%s %s", A, B) != EOF) {
// 预处理
int n = strlen(A);
for (int i = 0; i < n - 1; i++) {
A[n + i] = A[i];
}
n = 2 * n - 1;
A[n] = '\0';
// 计算fail数组
make_fail(B);
// 求解
bool flag = kmp(A, B);
reverse(A, A + n);
flag |= kmp(A, B);
// 输出
if (flag) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}
// 计算fail数组
void make_fail(char* mode) {
// 初始化
fail[0] = 0;
// 递推
for (int i = 1, j = 0; mode[i] != '\0'; i++) {
while (j > 0 && mode[i] != mode[j]) {
j = fail[j - 1];
}
if (mode[i] == mode[j]) {
fail[i] = ++j;
} else {
fail[i] = 0;
}
}
}
// KMP
bool kmp(char* str, char* mode) {
// 递推
for (int i = 0, j = 0; str[i] != '\0'; i++) {
while (j > 0 && str[i] != mode[j]) {
j = fail[j - 1];
}
if (str[i] == mode[j]) {
j++;
}
if (mode[j] == '\0') {
return true;
}
}
// 返回
return false;
}
cbecbcdebadeaecadcbdbeccdaeaeadcedcdeaadeadebaeaddcaabbdceeadcbaecdeabeccacaeeedaaebaaabbecaebeeadac
<999924 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
beecedeebbcedadeebcecabcbaeaebbedacebeacdabbecceebecddbeacccecdaeebaadaabacaecaeeaedeababcdaccdbcdcc
<999924 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
abbcaedcdaddbebdaadcbbdaebddcccceabcaccbcedadecdebcbceabbdcabcccdcaeeaadddbeebbbeeabcacaddddceeebbcb
<999924 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
ccbedebdaedcdbedddbdcdbedaaeadcdeeccdbaacbcebcbcaccbbaccdcecdcdbcabdaadeddbaccceebaabdedcccdbcadeeac
<999924 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
bbcdacbdabeaacecddaecceeaadbbceadbbcdceedaadcabbdbccbbdcaebceedceeaabecccbdbccbddeadacecaddcadcbeaad
<999924 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
abddebdbccbdaeacacaabebadccbddeaabcacddcbddabaeacccebdedaeecabbbebddddbddaaacdcacabcddbcddeccceedcad
<999924 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
eaeceebdcaeaacedadabcaaceeaeedadebadbdeaeebbbedbecaeddcecbdebcadbbeaabdbcddacbcdbbaebadbccecaedbdebd
<999924 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
bebeedabcdceabccebddbaacaacdacabbbedcbcdadaebdbceceaddbbcadcbbddceaaecacceeecacdbcdedcdeacbbbbbabbdc
<999924 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
cbcbddbbddcddceedbbcaddeccdebedaeacdeeceadaddcddcdcdabdadecacbbeecddddeecccdadecbcaecaeacacdcaedabba
<999924 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
cacccaeaddeaacabbbeeeecbbccbdcedaeaaacbcbdbaecaabbdacdbbceaacbbabccabcbaebaebadeebeadcbceeeebbeceade
<999924 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
cbcbbacabaabbcbccacbbaaaccaacabccaaaabacbacbacacccabbbbbaaacbacbaabaaccbbcaacbcacbbaabacbccaccaaabcc
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
bbbaaaccaabcbbacbcbccbabaaacbcccbbabacccabcacbccabcbbbaaacaccbbcbccccbaabacacbabaccbbabaaaabbcbbaabc
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
cbccbccabacccacbbccaccbbbcbcbbcabcccbbcbccccaacccaaccacaaacbbbbbacaacbabcbcbabbaaacaaabcbbcbaacbacbc
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
bcacbbbcbbcbcbccbccabacbcabbcccccbbcaaabacbcacbbbcbcaabcccabbaacccacbbccacaccbbbacacbcacaaabcccacbab
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
aaabacbbacbabbccbcabbbcaccacbbababcccbbbabbcbccabbcbaccbbacccbbcbaaacbcbacbccbacacccabcbbacbccbaacca
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
acccacbbbacbcaccacaacaaabbbabbcccabcaaaacbaccababcbacaacaabacabaaabccabcccabaccbcbbccaccaacccabaacbb
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
acbbbbcbaaabbcccaaaabbcbcccccabcaacccbacbacabbabacccabacabacaacaaacbabbbcabbcabaaacccaabcbccbaaabcac
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
abbacbcabcabaaabbcabbcbaaaaabcabcbabcbbabbcbabaccaccbcccbaabcbacbbaaccaacbcabaabbaccacbcccccabccaaba
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
ccaacacbbaaccbbbacabcbccbccaccbbbbcaacaacbcccacabcababaaabaabbbacccbbacbccabcbbccbaaccaabcaacabababc
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
cccbcbbbaccccbcbaccbbbabcbbcbcaacabcbabaccaaababcbaabbbcbbccbbaaabccaabcccacabaacacbbcbbcaacbacaacab
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
cdcabcbbbbdbbccdbcabbbadadacabacbbddaddbabbabbadcaadacbadcbcaabdbdacabddabbbdbadabcaddaacddbcbacaddd
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
bbdccbbcadbbdcdbcbdbbcbaddaacabccccadabddadcacdddacbacacddbcacdbbcacbcacdcbbccbbbbbdababcbddcabbbbcb
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
abbcabdcbaacccadcbabbacacdcbdcaacaacbabbaabdaabadacdcbabddbbcccbdddbbabbcacbdaaaaaadcdaacadddddccbcb
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
adacdddbdddcacbcaaaccbbdabddaaaabbcdcadbbcbbbacbcddbbaadccbcddccccbdcaabacadaabbaccdcadbcdabaabbcaaa
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
bccbdbbabbcdbcababdcdcbcccccadcababcdabdacabdbdbbaaaaccdbbdbdcabacdcbcddbcacccbbccadcdbddcbcabcccdcc
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
dcbbccdcabbccdddbbbcabcbcbdadccbdaabbdbbabdddcbcbadcddcccbcddcdcccbdbbbabcadcacddcaadabaaabdcccdcbbb
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
ddddbcdadbbcbaacdcdadabddacbadbddaddcdbccacadbdbdaadbbbaccbabdabdacbbbcbddcabdadabaabbacacbbaabcdadb
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
ccdadcbdbdaadaacbdabaccbbccdbdbbabbbaadcbaddcccbabacddbbbbcccbaadbaadccbcaaabcdaaabdbbdcbaabbddbadda
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
bacabdcbbaabbbbccacadddbdddacabcababcabbbdaccbdbaddcdddbabcabbbdddabadbccdcadaaddcbbbabbbbaddadaaacc
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
acdbccbdbbbdccbcbbbcbdbcccadbbaacdcbcccdcbbaabccaccdccbccaadbaabbadabcdaaacbddaabbabbccaabddbddacada
<999914 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
ccedfccdcadfaedaedfdbfadfceacafcfafdabdaecdcfddcaafbcadabdfedbbbbbdeedbfcddbadfbdeebeeaccefeeeebcadd
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
efddacadfdbdfdcfcbeacfecfbfcaaeefcebfafeafacaacfdfdabeeffbcbedbbcfdffdabeccdaaaaeffdfedeaecbecbbeded
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
dfeeeccbbcafabdaeccbffabaecccfdcfcabbbfcbadbeeaadacdbbcefeeedccddfaedabaeefaadabfbfcecbcaebfedcdaaaf
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
cddaababeefbecfcbaeedbcdefdbaaebebeaadbcfadfbfbfdefcecfababdbcbbaafcacdfebccbadcdaecffeeceebcaeeaace
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
cabbceaffcfafaafacddfcbdbfbdcbcebbacfecfddacadebcdbaddddcbcceaabedefadccadaefbdcfdedebfdbebcccafdacf
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
ddeeabaddacfdafefdcebcebdcfeacafdbcbdeecfdbbcbacadafaedbfbccffaafcddddcfbebdbafaadcaecbdefddfcafbcab
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
caeedcaaaefeafcbadbcbfaaedbddccfcecabdfeaecfcbdafabeaeffddbaffcbdfadabcacecfccdfecbaecfcbaddffddacab
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
acedaaafebeaacccbdfffbbdccabbbfdbebaececbafcfffbfdcdadccbaedbdfbcbabcbabbfcffafdefdddfebeeadbfdcffbc
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
eccdbbedfbbfffcfaecdddcbefcafeeccaffcedbacabcbfcdccaaefdbadbccfffedfcdabccffcfcbbcfbcaaedcfedcbadfae
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
aaccdaaffeaefdbcfabedfdefbcdbaabafabcedcdbdfceaddeefcaddbfffdaededeebaefdaedebbfbcecbededceecbceacee
<999914 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
<1499904 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
<1499904 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
<1499904 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
<1499904 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg
<1499904 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj
<1499904 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu
<1499904 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
<1499904 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
<1499904 bytes omitted>
用户输出
No
系统信息
Exited with return code 0
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
<1499904 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
<1499904 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
<1499904 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
<1499904 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
<1499904 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
<1499904 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
<1499904 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
<1499904 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
<1499904 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
<1499904 bytes omitted>
用户输出
Yes
系统信息
Exited with return code 0