UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#206120#3169. 密码marcuse100366ms17652kbC++966b2024-07-20 19:54:512024-07-20 20:29:42

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: 2ms
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: 94ms
memory: 17648kb

input:

crwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkd...

output:

crwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkd...

result:

ok single line: 'crwffzvkdcsiccrwffzvkdcsiccrwf...csiccrwffzvkdcsiccrwffzvkdcsicc'

Test #7:

score: 10
Accepted
time: 79ms
memory: 17648kb

input:

yxwsxywxkrzlqsiwdspucezlkgshfzctbpyildxbwnmlkecqqotojgxbemfzodkrcushnizzugwuaojfqblyhlfbpqwactpcdgur...

output:

yxwsxywxkrzlqsiwdspucezlkgshfzctbpyildxbwnmlkecqqotojgxbemfzodkrcushnizzugwuaojfqblyhlfbpqwactpcdgur...

result:

ok single line: 'yxwsxywxkrzlqsiwdspucezlkgshfz...rzlqsiwdspucezlkgshfzctbpyildxb'

Test #8:

score: 10
Accepted
time: 67ms
memory: 17652kb

input:

bnlwrkorxmhhlvcpacuxjzeuuggrobdywjzqaafaamhoqebzupzyqwfcmanbuocdodaooxxuukbqevlidlspvlquwcabsylqiadv...

output:

bnlwrkorxmhhlvcpacuxjzeuuggrobdywjzqaafaamhoqebzupzyqwfcmanbuocdodaooxxuukbqevlidlspvlquwcabsylqiadv...

result:

ok single line: 'bnlwrkorxmhhlvcpacuxjzeuuggrob...mhhlvcpacuxjzeuuggrobdywjzqaafa'

Test #9:

score: 10
Accepted
time: 60ms
memory: 17652kb

input:

sqomhzwerrhbmqvtukrgmkxrbgfrwdsrrkqwwxugmhzfgkjtzgpzaqbtworlitprwutprgamridxmnrzjkwnvlotnkscgqcbsnjs...

output:

-1

result:

ok single line: '-1'

Test #10:

score: 10
Accepted
time: 64ms
memory: 17648kb

input:

qtkmtpbygecktzwbjnfhkixcaikrrbwrblidemsjdvojwnctrlkvcvuvdppudyjlstpulczgiofeuuypedxsktxhpzofouwrzfjj...

output:

qtkmtpbygecktzwbjnfhkixcaikrrbwrblidemsjdvojwnctrlkvcvuvdppudyjlstpulczgiofeuuypedxsktxhpzofouwrzfjj...

result:

ok single line: 'qtkmtpbygecktzwbjnfhkixcaikrrb...crqfygiiennmbvsutqtfgvvrwlocprl'

Extra Test:

score: 0
Extra Test Passed