QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#722734#9522. A Simple String Problemgrass8cowAC ✓1456ms104852kbC++172.2kb2024-11-07 20:04:462024-11-10 22:38:46

Judging History

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

  • [2024-11-10 22:38:46]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1456ms
  • 内存:104852kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-07 20:04:46]
  • 评测
  • 测评结果:100
  • 用时:1370ms
  • 内存:105100kb
  • [2024-11-07 20:04:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int sa[N],t[N],tr[N],rk[N],m,h[N],st[N][20];
char c[N];
int lg[N];
int lcp(int x,int y){
	x=rk[x],y=rk[y];if(x>y)swap(x,y);x++;
	int k=lg[y-x+1];
	return min(st[x][k],st[y-(1<<k)+1][k]);
}
void SA(int n){
	lg[0]=-1;
	for(int i=1;i<=n;i++)lg[i]=lg[i>>1]+1;
	m=128;
	memset(t,0,sizeof(t));
	for(int i=1;i<=n;i++)t[rk[i]=c[i]]++;
	for(int i=1;i<=m;i++)t[i]+=t[i-1];
	for(int i=n;i;i--)sa[t[rk[i]]--]=i;
	for(int k=1;;k<<=1){
		int o=0;
		for(int i=n-k+1;i<=n;i++)tr[++o]=i;
		for(int i=1;i<=n;i++)if(sa[i]>k)tr[++o]=sa[i]-k;
		for(int i=1;i<=m;i++)t[i]=0;
		for(int i=1;i<=n;i++)t[rk[i]]++;
		for(int i=1;i<=m;i++)t[i]+=t[i-1];
		for(int i=n;i;i--)sa[t[rk[tr[i]]]--]=tr[i];
		swap(tr,rk),rk[sa[1]]=o=1;
		for(int i=2;i<=n;i++)
		rk[sa[i]]=(tr[sa[i-1]]==tr[sa[i]]&&tr[sa[i-1]+k]==tr[sa[i]+k])?o:(++o);
		if(o==n)break;m=o; 
	}
	for(int i=1,k=0;i<=n;i++){
		if(k)k--;int j=sa[rk[i]-1];
		while(c[i+k]==c[j+k]&&i+k<=n&&j+k<=n)k++;
		st[rk[i]][0]=k;
	}
	for(int j=1;j<20;j++)for(int i=1;i+(1<<j)-1<=n;i++)
	st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int n;
int Lcp(bool f1,bool f2,bool f3,int x,int y){
	if(f1)x=n+1-x,y=n+1-y;
	if(x>n||y>n)return 0;
	if(!f1)return min(min(n-x+1,n-y+1),lcp(x+(f2?(n*2):0),y+(f3?(n*2):0)));
	return min(min(n-x+1,n-y+1),lcp(x+n+(f2?(n*2):0),y+n+(f3?(n*2):0)));
}
char a[200100],b[200100];
//把a正反串和b拼进来跑sa 
int mx;
void Sol(){
	int L=0;
	for(int i=1;i<=n;i++)c[++L]=a[i];c[++L]='1';
	c[++L]='2';for(int i=n;i;i--)c[++L]=a[i];
	c[++L]='3';for(int i=1;i<=n;i++)c[++L]=b[i];
	for(int i=n;i;i--)c[++L]=b[i];c[++L]='4';
	SA(L);n++;
	for(int k=1;k<=n;k++){
		bool gg=0;
		for(int i=0;i+k<=n;i+=k){
			int l1=Lcp(0,0,0,i+1,i+k+1),l2=Lcp(1,0,0,i,i+k);
			if(l1+l2>=k||Lcp(0,0,1,i+1+l1,i+k+1+l1)>=k-l1-l2)gg=1;
			l1=Lcp(0,0,1,i+1,i+k+1),l2=Lcp(1,0,1,i,i+k);
			if(l1+l2>=k||Lcp(1,0,0,i-l2,i+k-l2)>=k-l1-l2)gg=1;
		}
		if(gg)mx=max(mx,k);
	}
	n--;
}
int main(){
	scanf("%d%s%s",&n,a+1,b+1);
	Sol();
	reverse(a+1,a+n+1),reverse(b+1,b+n+1);
	for(int i=1;i<=n;i++)swap(a[i],b[i]);
	Sol();
	printf("%d\n",mx*2);
	return 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 32584kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 4ms
memory: 34676kb

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 3ms
memory: 32520kb

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 8ms
memory: 32484kb

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

score: 0
Accepted
time: 3ms
memory: 36660kb

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 6ms
memory: 34632kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 1445ms
memory: 104420kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 1452ms
memory: 101636kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 1456ms
memory: 102048kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 1229ms
memory: 103096kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 1143ms
memory: 104852kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 1454ms
memory: 102384kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 1111ms
memory: 102000kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 8ms
memory: 32480kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 8ms
memory: 32628kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 8ms
memory: 34612kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 7ms
memory: 32448kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 8ms
memory: 34544kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

score: 0
Accepted
time: 4ms
memory: 32508kb

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 7ms
memory: 32632kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 7ms
memory: 34636kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed