ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#205957 | #3169. 密码 | yhmm | 100 | 283ms | 7772kb | C++11 | 791b | 2024-07-20 18:17:07 | 2024-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