ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#206118 | #3169. 密码 | marcuse | 100 | 373ms | 17652kb | C++ | 966b | 2024-07-20 19:54:20 | 2024-07-20 20:29:31 |
answer
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N = 1000000 + 10;
const int P = 131;
string s;
int Pre[N],ans;
int lft,rgt;
int Base[N];
int calc(int lft,int rgt) {
int length = rgt - lft + 1;
return Pre[rgt] - Pre[lft - 1] * Base[length];
}
bool check(int len) {
if(calc(1,len) != calc(s.size() - len + 1,s.size())) return false;
int res = calc(1,len);
for(int i = 2; i + len - 1 < s.size(); i++) {
int rgt = i + len - 1;
if(calc(i,rgt) == res) return true;
}
return false;
}
signed main() {
cin >> s;
Base[0] = 1;
for(int i = 1; i <= s.size() + 1; i++) {
Base[i] = Base[i - 1] * P;
}
for(int i = 1; i <= s.size(); i++) {
Pre[i] = Pre[i - 1] * P + s[i - 1] - 'a' + 1;
}
int flag = false;
for(ans = s.size() - 2; ans >= 1; ans--) {
if(check(ans)){
for(int i = 0; i < ans; i++) cout << s[i];
return 0;
}
}
puts("-1");
return 0;
}
//3 abcbac
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1208kb
input:
aaaaaaabbbabbbbabbabaaaaaabbaabbaaaaaaaaaabbbabbbbabbabaaaaaabbaabbaaaaaaaaaabbbabbbbabbabaaaaaabbaa
output:
aaaaaaabbbabbbbabbabaaaaaabbaa
result:
ok single line: 'aaaaaaabbbabbbbabbabaaaaaabbaa'
Test #2:
score: 10
Accepted
time: 1ms
memory: 1208kb
input:
aababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaaba
output:
aababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaaba
result:
ok single line: 'aababaaababaaababaaababaaababa...abaaababaaababaaababaaababaaaba'
Test #3:
score: 10
Accepted
time: 0ms
memory: 1220kb
input:
yhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhgg...
output:
yhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhgg...
result:
ok single line: 'yhggbzbxmpjummidyhggbzbxmpjumm...pjummidyhggbzbxmpjummidyhggbzbx'
Test #4:
score: 10
Accepted
time: 0ms
memory: 1224kb
input:
prvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfc...
output:
prvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfc...
result:
ok single line: 'prvokxwfcyjyeprvokxwfcyjyeprvo...fcyjyeprvokxwfcyjyeprvokxwfcyjy'
Test #5:
score: 10
Accepted
time: 0ms
memory: 1220kb
input:
kbnoefznwkhnwgqynrxdgdqjyijlhjyiamdcympayyezqrpsaxgoxtdfwnxurbuowqcyhlqzjgghqcpvbhoydegeefqcpmohqpep...
output:
kbnoefznwkhnwgqynrxdgdqjyijlhjyiamdcympayyezqrpsaxgoxtdfwnxurbuowqcyhlqzjgghqcpvbhoydegeefqcpmohqpep...
result:
ok single line: 'kbnoefznwkhnwgqynrxdgdqjyijlhj...ntpjpztjkkfqtcijbvnytdhyeqikcfq'
Test #6:
score: 10
Accepted
time: 106ms
memory: 17652kb
input:
crwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkd...
output:
crwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkd...
result:
ok single line: 'crwffzvkdcsiccrwffzvkdcsiccrwf...csiccrwffzvkdcsiccrwffzvkdcsicc'
Test #7:
score: 10
Accepted
time: 73ms
memory: 17648kb
input:
yxwsxywxkrzlqsiwdspucezlkgshfzctbpyildxbwnmlkecqqotojgxbemfzodkrcushnizzugwuaojfqblyhlfbpqwactpcdgur...
output:
yxwsxywxkrzlqsiwdspucezlkgshfzctbpyildxbwnmlkecqqotojgxbemfzodkrcushnizzugwuaojfqblyhlfbpqwactpcdgur...
result:
ok single line: 'yxwsxywxkrzlqsiwdspucezlkgshfz...rzlqsiwdspucezlkgshfzctbpyildxb'
Test #8:
score: 10
Accepted
time: 65ms
memory: 17652kb
input:
bnlwrkorxmhhlvcpacuxjzeuuggrobdywjzqaafaamhoqebzupzyqwfcmanbuocdodaooxxuukbqevlidlspvlquwcabsylqiadv...
output:
bnlwrkorxmhhlvcpacuxjzeuuggrobdywjzqaafaamhoqebzupzyqwfcmanbuocdodaooxxuukbqevlidlspvlquwcabsylqiadv...
result:
ok single line: 'bnlwrkorxmhhlvcpacuxjzeuuggrob...mhhlvcpacuxjzeuuggrobdywjzqaafa'
Test #9:
score: 10
Accepted
time: 63ms
memory: 17652kb
input:
sqomhzwerrhbmqvtukrgmkxrbgfrwdsrrkqwwxugmhzfgkjtzgpzaqbtworlitprwutprgamridxmnrzjkwnvlotnkscgqcbsnjs...
output:
-1
result:
ok single line: '-1'
Test #10:
score: 10
Accepted
time: 65ms
memory: 17652kb
input:
qtkmtpbygecktzwbjnfhkixcaikrrbwrblidemsjdvojwnctrlkvcvuvdppudyjlstpulczgiofeuuypedxsktxhpzofouwrzfjj...
output:
qtkmtpbygecktzwbjnfhkixcaikrrbwrblidemsjdvojwnctrlkvcvuvdppudyjlstpulczgiofeuuypedxsktxhpzofouwrzfjj...
result:
ok single line: 'qtkmtpbygecktzwbjnfhkixcaikrrb...crqfygiiennmbvsutqtfgvvrwlocprl'
Extra Test:
score: 0
Extra Test Passed