Xidian Online Judge WebBoard
 Problem 1012 >> 为什么会RE诶 zhang_fan0105 @ 2019-01-13 13:51:28 [ Quote ] [ Edit ] [ Delete ] 1# 照着前人的代码几乎要原封不动的改下来了。。 #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn = 400010; unsigned int hash_arr[maxn]; unsigned int ratio[maxn]; typedef pairP; int N; inline void init(string str); P solve(int L); int main() { ios_base::sync_with_stdio(false); string str; str.resize(maxn); while (cin >> str) { memset(hash_arr, 0, sizeof(hash_arr)); N = str.length(); init(str); P ans(-1, -1); for (int i = 1; i <= N / 2; i++) { P t = solve(i); if (ans < t) ans = t; } if (ans.first != -1) { for (int i = N - ans.second; i < N; i++) { cout << str[i]; } cout << " " << ans.first; } else cout << -1; cout << "\n"; } } inline void init(string str) { unsigned int seed = 31; for (int i = N - 1; i >= 0; i--) { hash_arr[i] = hash_arr[i + 1] * seed + str[i]; } ratio[1] = 31; for (int i = 2; i <= N; i++) { ratio[i] = ratio[i - 1] * seed; } } P solve(int len) { int r = N - len; int l = N - 2 * len; unsigned int hash_l, hash_r; hash_r = hash_arr[r]; hash_l = hash_arr[l] - hash_arr[l + len] * ratio[len]; int cnt = 1; while (hash_r == hash_l) { cnt++; l -= len; if (l >= 0) hash_l = hash_arr[l] - hash_arr[l + len] * ratio[len]; else break; } if (cnt == 1) return P(-1, -1); else return P(cnt, len); } worse @ 2019-01-14 19:12:33 [ Quote ] [ Edit ] [ Delete ] 2# 我不是说了这 OJ 有 bug 不能 std::ios::sync_with_stdio(false) 吗。。。
[Top] [Previous Page] [Next Page]