Xidian Online Judge WebBoard
[ New Thread ]
Problem 1012 >> 为什么会RE诶
zhang_fan0105 @ 2019-01-13 13:51:28
[ Quote ] [ Edit ] [ Delete ] 1#
照着前人的代码几乎要原封不动的改下来了。。
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#include<climits>
#include<cmath>
#include<map>
#include<set>
using namespace std;
const int maxn = 400010;
unsigned int hash_arr[maxn];
unsigned int ratio[maxn];
typedef pair<int, int>P;
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]
Anything about the Problems, Please Contact Admin:admin
All Copyright Reserved 2010-2014 Xidian ACM Online Judge TEAM
GPL2.0 2003-2014 HUSTOJ Project TEAM