UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#205957#3169. 密码yhmm100283ms7772kbC++11791b2024-07-20 18:17:072024-07-20 20:07:50

answer

#include<bits/stdc++.h>
using namespace std;
int pos,f;
string s,b;
vector<int>PI;
vector<int>PrefixFunction(string s)
{
	vector<int>pi(s.size());
	for(int i=1,j=0;i<s.size();i++)
	{
		while(j>0&&s[i]!=s[j])
		{
			j=pi[j-1];
		}
		if(s[i]==s[j])
		{
			j++;
		}
		pi[i]=j;
	}
	return pi;
}
int main(){
	cin>>s;
	PI=PrefixFunction(s);
	pos=PI[s.size()-1];
	while(pos)
	{
		b=s.substr(0,pos),f=0;
		for(int i=0,j=0;i<s.size();i++)
		{
			while(j&&s[i]!=b[j])
			{
				j=PI[j-1];
			}
			if(s[i]==b[j])
			{
				j++;
			}
			if(j==b.size())
			{
				if(i==pos-1)
				{
					j=PI[j-1];
				}
				else if(i!=s.size()-1)
				{
					f=1;
				}
			}
		}
		if(f)
		{
			cout<<b;
			return 0;
		}
		pos=PI[pos-1];
	}
	cout<<-1;
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1212kb

input:

aaaaaaabbbabbbbabbabaaaaaabbaabbaaaaaaaaaabbbabbbbabbabaaaaaabbaabbaaaaaaaaaabbbabbbbabbabaaaaaabbaa

output:

aaaaaaabbbabbbbabbabaaaaaabbaa

result:

ok single line: 'aaaaaaabbbabbbbabbabaaaaaabbaa'

Test #2:

score: 10
Accepted
time: 0ms
memory: 1216kb

input:

aababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaaba

output:

aababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaababaaaba

result:

ok single line: 'aababaaababaaababaaababaaababa...abaaababaaababaaababaaababaaaba'

Test #3:

score: 10
Accepted
time: 0ms
memory: 1216kb

input:

yhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhgg...

output:

yhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhggbzbxmpjummidyhgg...

result:

ok single line: 'yhggbzbxmpjummidyhggbzbxmpjumm...pjummidyhggbzbxmpjummidyhggbzbx'

Test #4:

score: 10
Accepted
time: 0ms
memory: 1220kb

input:

prvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfc...

output:

prvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfcyjyeprvokxwfc...

result:

ok single line: 'prvokxwfcyjyeprvokxwfcyjyeprvo...fcyjyeprvokxwfcyjyeprvokxwfcyjy'

Test #5:

score: 10
Accepted
time: 0ms
memory: 1216kb

input:

kbnoefznwkhnwgqynrxdgdqjyijlhjyiamdcympayyezqrpsaxgoxtdfwnxurbuowqcyhlqzjgghqcpvbhoydegeefqcpmohqpep...

output:

kbnoefznwkhnwgqynrxdgdqjyijlhjyiamdcympayyezqrpsaxgoxtdfwnxurbuowqcyhlqzjgghqcpvbhoydegeefqcpmohqpep...

result:

ok single line: 'kbnoefznwkhnwgqynrxdgdqjyijlhj...ntpjpztjkkfqtcijbvnytdhyeqikcfq'

Test #6:

score: 10
Accepted
time: 63ms
memory: 7772kb

input:

crwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkd...

output:

crwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkdcsiccrwffzvkd...

result:

ok single line: 'crwffzvkdcsiccrwffzvkdcsiccrwf...csiccrwffzvkdcsiccrwffzvkdcsicc'

Test #7:

score: 10
Accepted
time: 62ms
memory: 7092kb

input:

yxwsxywxkrzlqsiwdspucezlkgshfzctbpyildxbwnmlkecqqotojgxbemfzodkrcushnizzugwuaojfqblyhlfbpqwactpcdgur...

output:

yxwsxywxkrzlqsiwdspucezlkgshfzctbpyildxbwnmlkecqqotojgxbemfzodkrcushnizzugwuaojfqblyhlfbpqwactpcdgur...

result:

ok single line: 'yxwsxywxkrzlqsiwdspucezlkgshfz...rzlqsiwdspucezlkgshfzctbpyildxb'

Test #8:

score: 10
Accepted
time: 52ms
memory: 7088kb

input:

bnlwrkorxmhhlvcpacuxjzeuuggrobdywjzqaafaamhoqebzupzyqwfcmanbuocdodaooxxuukbqevlidlspvlquwcabsylqiadv...

output:

bnlwrkorxmhhlvcpacuxjzeuuggrobdywjzqaafaamhoqebzupzyqwfcmanbuocdodaooxxuukbqevlidlspvlquwcabsylqiadv...

result:

ok single line: 'bnlwrkorxmhhlvcpacuxjzeuuggrob...mhhlvcpacuxjzeuuggrobdywjzqaafa'

Test #9:

score: 10
Accepted
time: 56ms
memory: 7088kb

input:

sqomhzwerrhbmqvtukrgmkxrbgfrwdsrrkqwwxugmhzfgkjtzgpzaqbtworlitprwutprgamridxmnrzjkwnvlotnkscgqcbsnjs...

output:

-1

result:

ok single line: '-1'

Test #10:

score: 10
Accepted
time: 50ms
memory: 7088kb

input:

qtkmtpbygecktzwbjnfhkixcaikrrbwrblidemsjdvojwnctrlkvcvuvdppudyjlstpulczgiofeuuypedxsktxhpzofouwrzfjj...

output:

qtkmtpbygecktzwbjnfhkixcaikrrbwrblidemsjdvojwnctrlkvcvuvdppudyjlstpulczgiofeuuypedxsktxhpzofouwrzfjj...

result:

ok single line: 'qtkmtpbygecktzwbjnfhkixcaikrrb...crqfygiiennmbvsutqtfgvvrwlocprl'

Extra Test:

score: 0
Extra Test Passed