- #include using namespace std;
- char s[1000005],
- t[1000005];
- int nex[1000005];
- int l;
- char f[20];
- void la(int n, int b) {
- static char c[16] = {'0',
- '1',
- '2',
- '3',
- '4',
- '5',
- '6',
- '7',
- '8',
- '9',
- 'A',
- 'B',
- 'C',
- 'D',
- 'E',
- 'F'
- };
- l = 0;
- while (n) {
- f[l++] = c[n % b];
- n = n / b;
- }
- }
- void pre(char * p) {
- int i,
- n,
- k;
- n = strlen(p);
- nex[1] = nex[0] = 0;
- k = 0;
- for (i = 2; i <= n; i++) {
- for (; k != 0 && p[k] != p[i - 1]; k = nex[k]);
- if (p[k] == p[i - 1]) k++;
- nex[i] = k;
- }
- }
- int kmp(char * text, char * p) {
- int m,
- n,
- s,
- q;
- m = strlen(p);
- n = strlen(text);
- q = s = 0;
- while (s < n) {
- for (q = nex[q]; q);
- if (q == 0) s++;
- else if (q == m) {
- return 1;
- }
- }
- return 0;
- }
- int main() {
- int n;
- scanf("%d", &n);
- getchar();
- for (int i = 0;; i++) {
- char c = getchar();
- if (c == '\n') {
- t[i] = 0;
- break;
- }
- t[i] = c;
- }
- pre(t);
- for (int j = 16; j > 1; j--) {
- int b = 0;
- for (int i = 1; i <= n; i++) {
- la(i, j);
- for (int k = l - 1; k >= 0; k--) s[b++] = f[k];
- }
- s[b] = 0;
- if (kmp(s, t)) return 0 * puts("yes");
- }
- return 0 * puts("no");
- }
来源: http://www.bubuko.com/infodetail-2137748.html