竞赛讨论区 > 第十二个例子过不去,求助
头像
zoybzo
发布于 2020-02-22 10:27
+ 关注

第十二个例子过不去,求助

#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) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐