#include <bits/stdc++.h>
using namespace std;
const int M = 1e6 + 10;
string s;
int nextval[M];
int kmp(string ps, string ss) {
if (ps.size() < ss.size()) return 0;
int i = 0, j = 0;
while (i < ps.size()) {
if (j == -1 || ps[i] == ss[j]) {
i++;
j++;
if (j == ss.size())
return 1;
} else {
j = nextval[j];
}
}
return 0;
}
void getNext(string ss) {
int i = -1, j = 0;
nextval[0] = -1;
while (j != ss.size() - 1) {
if (i == -1 || ss[i] == ss[j]) {
i++;
j++;
if (ss[i] == ss[j]) {
nextval[j] = nextval[i];
} else {
nextval[j] = i;
}
} else {
i = nextval[i];
}
}
}
void init(string ss) {
ss.clear();
}
char charge(int x) {
return (char) x;
}
void binary(int n, int d) {
string a;
while (n > 0) {
int num = n % d;
n /= d;
if (num < 10) num = num + '0';
else num = num - 10 + 'A';
a = charge(num) + a;
}
::s += a;
}
int main() {
int n;
cin >> n;
string t;
cin >> t;
bool flag = false;
for (int d = 2; d < 17; d++) {
init(::s);
for (int i = 1; i <= n; i++) {
binary(i, d);
}
getNext(t);
if ((flag = kmp(::s, t))) break;
}
if (flag) cout << "yes";
else cout << "no";
}
总是卡在第十二个case, 求助
全部评论
(1) 回帖