QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#699416 | #9522. A Simple String Problem | lrher | AC ✓ | 1088ms | 18088kb | C++14 | 3.9kb | 2024-11-02 08:52:28 | 2024-11-06 21:49:46 |
Judging History
你现在查看的是测评时间为 2024-11-06 21:49:46 的历史记录
- [2024-11-10 22:36:11]
- hack成功,自动添加数据
- (/hack/1163)
- [2024-11-06 21:48:00]
- hack成功,自动添加数据
- (/hack/1142)
- [2024-11-02 08:52:28]
- 提交
answer
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<string>
#include<bitset>
#include<vector>
#include<cstdio>
#include<random>
#include<complex>
#include<cstdlib>
#include<climits>
#include<iomanip>
#include<cstring>
#include<cassert>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
const long long _base=107374183;
int writetemp[30];
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;
return x;
}
inline void write(long long x)
{
int tot=(x==0);
writetemp[1]=0;
while(x) writetemp[++tot]=x%10,x/=10;
while(tot) putchar(writetemp[tot--]+'0');
putchar('\n');
return ;
}
const int mod=1000000007,base=31;
int n,ans;
char a[1000010],b[1000010];
long long mul[1000010];
long long haa[1000010],hab[1000010];
long long pd(long long x)
{
if(x>=mod) return x-mod;
return x;
}
long long get_a(int l,int r)
{
return pd(haa[r]-haa[l-1]*mul[r-l+1]%mod+mod);
}
long long get_b(int l,int r)
{
return pd(hab[r]-hab[l-1]*mul[r-l+1]%mod+mod);
}
int solve(char *a,char *b)
{
for(int i=1;i<=n;i++) haa[i]=(haa[i-1]*base+a[i]-'a')%mod;
for(int i=1;i<=n;i++) hab[i]=(hab[i-1]*base+b[i]-'a')%mod;
for(int k=n;k>=1;k--)
{
for(int now=k;now+k-1<=n;now+=k) if(get_a(now-k+1,now)==get_b(now,now+k-1)) return k+k;
for(int now=k;now+k-1<=n;now+=k)
{
int nxt=now+k,nowlen=0;
int l=0,r=k;
while(l<r)
{
int mid=(l+r+1)>>1;
if(get_a(now-mid+1,now)==get_a(nxt-mid+1,nxt)) l=mid;
else r=mid-1;
}
now++,nxt++,nowlen=l;
l=0,r=min(k,n-nxt+1);
while(l<r)
{
int mid=(l+r+1)>>1;
if(get_a(now,now+mid-1)==get_a(nxt,nxt+mid-1)) l=mid;
else r=mid-1;
}
now+=l,nxt+=l-1,nowlen+=l;
l=0,r=min(k,n-nxt+1);
while(l<r)
{
int mid=(l+r+1)>>1;
if(get_a(now,now+mid-1)==get_b(nxt,nxt+mid-1)) l=mid;
else r=mid-1;
}
nowlen+=l;
if(nowlen>=k) return k+k;
}
for(int now=k;now+k-1<=n;now+=k)
{
int nxt=now+k,nowlen=0;
now++;
int l=0,r=min(k,n-nxt+1);
while(l<r)
{
int mid=(l+r+1)>>1;
if(get_a(now,now+mid-1)==get_b(nxt,nxt+mid-1)) l=mid;
else r=mid-1;
}
now--,nxt--,nowlen=l;
l=0,r=k;
while(l<r)
{
int mid=(l+r+1)>>1;
if(get_a(now-mid+1,now)==get_b(nxt-mid+1,nxt)) l=mid;
else r=mid-1;
}
now-=l,nxt-=l-1,nowlen+=l;
l=0,r=min(k,now);
while(l<r)
{
int mid=(l+r+1)>>1;
if(get_a(now-mid+1,now)==get_a(nxt-mid+1,nxt)) l=mid;
else r=mid-1;
}
nowlen+=l;
if(nowlen>=k) return k+k;
}
}
return 0;
}
int main()
{
// freopen("s.out","r",stdin);
// freopen("a.out","w",stdout);
scanf("%d",&n),mul[0]=1;
scanf("%s%s",a+1,b+1);
for(int i=1;i<=n;i++) mul[i]=mul[i-1]*base%mod;
ans=solve(a,b);
for(int i=1;i<=(n>>1);i++) swap(a[i],a[n-i+1]),swap(b[i],b[n-i+1]);
ans=max(ans,solve(b,a));
printf("%d\n",ans);
return 0;
}
/*
6
aaabab
aabbab
*/
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9968kb
input:
5 abcab acabc
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7888kb
input:
6 babbaa babaaa
output:
6
result:
ok single line: '6'
Test #3:
score: 0
Accepted
time: 2ms
memory: 10052kb
input:
2 ne fu
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 10044kb
input:
6 baabba baabab
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 1ms
memory: 10048kb
input:
6 aaabba aabbba
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 1ms
memory: 10056kb
input:
6 abaabb bbbaba
output:
4
result:
ok single line: '4'
Test #7:
score: 0
Accepted
time: 510ms
memory: 16872kb
input:
200000 wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...
output:
200000
result:
ok single line: '200000'
Test #8:
score: 0
Accepted
time: 507ms
memory: 15772kb
input:
199999 klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...
output:
200000
result:
ok single line: '200000'
Test #9:
score: 0
Accepted
time: 522ms
memory: 17464kb
input:
200000 yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...
output:
114514
result:
ok single line: '114514'
Test #10:
score: 0
Accepted
time: 1088ms
memory: 17500kb
input:
200000 cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 23ms
memory: 18024kb
input:
200000 bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...
output:
150050
result:
ok single line: '150050'
Test #12:
score: 0
Accepted
time: 36ms
memory: 17704kb
input:
200000 babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...
output:
131072
result:
ok single line: '131072'
Test #13:
score: 0
Accepted
time: 1007ms
memory: 18088kb
input:
200000 rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...
output:
8
result:
ok single line: '8'
Test #14:
score: 0
Accepted
time: 1ms
memory: 10044kb
input:
10 aaabaabaaa aabbbaaaba
output:
6
result:
ok single line: '6'
Test #15:
score: 0
Accepted
time: 1ms
memory: 10100kb
input:
17 ababbbaabbbaaaaba abbabbbbbaabaabba
output:
10
result:
ok single line: '10'
Test #16:
score: 0
Accepted
time: 0ms
memory: 10096kb
input:
22 aaabbbaaaababbabbbbbbb bbaabbbbbaaabbbabaaaaa
output:
8
result:
ok single line: '8'
Test #17:
score: 0
Accepted
time: 0ms
memory: 9948kb
input:
15 abaabaaaaabbbab abbbabbbabababa
output:
8
result:
ok single line: '8'
Test #18:
score: 0
Accepted
time: 0ms
memory: 10056kb
input:
5 aabba baaba
output:
6
result:
ok single line: '6'
Test #19:
score: 0
Accepted
time: 1ms
memory: 7900kb
input:
1 a a
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 9916kb
input:
100 baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa
output:
20
result:
ok single line: '20'
Test #21:
score: 0
Accepted
time: 1ms
memory: 10060kb
input:
32 babbbbbabbababaabbbaaaaabbaababa abbbaaababaabababbaaabaaabbaaaab
output:
18
result:
ok single line: '18'
Extra Test:
score: 0
Extra Test Passed