QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#756232#9522. A Simple String ProblemVegetable_DogAC ✓1017ms6688kbC++172.3kb2024-11-16 19:28:072024-11-16 19:28:08

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 19:28:08]
  • 评测
  • 测评结果:AC
  • 用时:1017ms
  • 内存:6688kb
  • [2024-11-16 19:28:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N=200005;
int n;
char s[2][N];

const int bs=131;
const int mod=998244353;
int pw[N];
int hs[2][N];
int geths(int x,int l,int r){ return (hs[x][r]-1ll*hs[x][l-1]*pw[r-l+1]%mod+mod)%mod; }

void pre_work(){
	pw[0]=1;
	for(int i=1;i<N;i++)pw[i]=1ll*pw[i-1]*bs%mod;
	for(int i=0;i<2;i++){
		hs[i][0]=s[i][0];
		for(int j=1;j<=n;j++)hs[i][j]=(1ll*hs[i][j-1]*bs+s[i][j])%mod;
	}
}
int getlcp(int x1,int p1,int x2,int p2){
	if(p1<0||p2<0||p1>n||p2>n)return 0;
	int l=1,r=n-max(p1,p2)+1,mid,res=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(geths(x1,p1,p1+mid-1)==geths(x2,p2,p2+mid-1))res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}
int getlcs(int x1,int p1,int x2,int p2){
	if(p1<0||p2<0||p1>n||p2>n)return 0;
	int l=1,r=min(p1,p2)+1,mid,res=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(geths(x1,p1-mid+1,p1)==geths(x2,p2-mid+1,p2))res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}

int ans=0;
int work1(){
	int res=0;
	for(int d=1;d*2<=n+1;d++){
		bool flag=0;
		for(int i=0;i+d<=n;i+=d){
			if(s[1][i]!=s[1][i+d])continue;
			int rm1=i+d+getlcp(1,i,1,i+d)-1;
			int lm1=i-getlcs(1,i,1,i+d)+1;
			int lm0=lm1-getlcs(0,lm1-1,1,lm1+d-1);
			if(rm1-lm0+1>=d*2){
				flag=1;
				break;
			}
		}
		if(flag)res=max(res,d*2);
	}
	return res;
}
int work2(){
	int res=0;
	for(int d=1;d*2<=n+1;d++){
		bool flag=0;
		for(int i=0;i+d<=n;i+=d){
			if(s[0][i]!=s[1][i+d])continue;
			int lm=getlcs(0,i,1,i+d);
			int rm=getlcp(0,i,1,i+d);
			if(lm+rm-1>=d){
				flag=1;
				break;
			}
			int t1=getlcs(0,i-lm,0,i+d-lm);
			int t2=getlcp(1,i+rm,1,i+d+rm);
			if(lm+rm-1+max(t1,t2)>=d){
				flag=1;
				break;
			}
		}
		if(flag)res=max(res,d*2);
	}
	return res;
}
int work3(){
	int res=0;
	for(int d=1;d*2<=n+1;d++){
		bool flag=0;
		for(int i=0;i+d<=n;i+=d){
			if(s[0][i]!=s[0][i+d])continue;
			int lm0=i-getlcs(0,i,0,i+d)+1;
			int rm0=i+d+getlcp(0,i,0,i+d)-1;
			int rm1=rm0+getlcp(1,rm0+1,0,rm0-d+1);
			if(rm1-lm0+1>=d*2){
				flag=1;
				break;
			}
		}
		if(flag)res=max(res,d*2);
	}
	return res;
}

int main(){
	scanf("%d",&n);
	scanf("%s%s",s[0],s[1]+1);
	s[0][n]='$'; s[1][0]='#';
	pre_work();
	ans=max(ans,work1());
	ans=max(ans,work2());
	ans=max(ans,work3());
	printf("%d",ans);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4736kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 0ms
memory: 5996kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5924kb

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 1ms
memory: 6028kb

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4604kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 1ms
memory: 5916kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 99ms
memory: 6600kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 99ms
memory: 6460kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 95ms
memory: 6540kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 811ms
memory: 6528kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 1017ms
memory: 6540kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 956ms
memory: 6688kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 96ms
memory: 6460kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 1ms
memory: 5844kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 1ms
memory: 4600kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 1ms
memory: 4604kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 1ms
memory: 4744kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 1ms
memory: 4484kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

score: 0
Accepted
time: 1ms
memory: 4664kb

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 1ms
memory: 4676kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 1ms
memory: 4668kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed