QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557514#8668. 回文路径Take_A_Single_60 0ms14688kbC++141.7kb2024-09-11 10:05:582024-09-11 10:05:58

Judging History

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

  • [2024-09-11 10:05:58]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:14688kb
  • [2024-09-11 10:05:58]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define db double
#define maxn 1000005
#define mod 1000000007
#define fir first
#define sec second
#define pr pair<int,int>
#define mk make_pair
#define inf 10000000000000000
using namespace std;
inline int read()
{
    int SS=0,WW=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')WW=-1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        SS=(SS<<1)+(SS<<3)+(ch^48);
        ch=getchar();
    }
    return SS*WW;
}
inline void write(int XX)
{
    if(XX<0)putchar('-'),XX=-XX;
    if(XX>9)write(XX/10);
    putchar(XX% 10 + '0');
}
int n,hs1[maxn],hs2[maxn],bs=131,pw[maxn],ans,nxt[maxn];
char s1[maxn],s2[maxn],s[maxn];
int geths1(int l,int r)
{
	return ((hs1[r]-hs1[l-1]*pw[r-l+1])%mod+mod)%mod;
}
int geths2(int l,int r)
{
	return ((hs2[r]-hs2[l-1]*pw[r-l+1])%mod+mod)%mod;
}
bool ck1(int l,int r)
{
	int len=r-l+1>>1;
	if(geths1(l,l+len-1)==geths1(r-len+1,r))return true;
	return false;
}
bool ck2(int l,int r)
{
	int len=r-l+1>>1;
	if(geths2(l,l+len-1)==geths2(r-len+1,r))return true;
	return false;
}
signed main()
{
	n=read(),cin>>s1+1>>s2+1,pw[0]=1;
	for(int i=1;i<=n;i++)hs1[i]=(hs1[i-1]*bs+s1[i])%mod,pw[i]=pw[i-1]*bs%mod;
	for(int i=1;i<=n;i++)hs2[i]=(hs2[i-1]*bs+s2[i])%mod;
	for(int i=n;i;i--)
		if(ck1(1,i))
		{
			ans=i;
			break;
		}
	for(int i=1;i<=n;i++)s[i]=s2[n-i+1];
	for(int i=2,j=0;i<=n;i++)
	{
		while(j&&s1[i]!=s1[j+1])j=nxt[j];
		if(s1[i]==s1[j+1])j++;
		nxt[i]=j;
	}
	for(int i=1,j=0;i<=n;i++)
	{
		while(j&&s[i]!=s1[j+1])j=nxt[j];
		if(s[i]==s1[j+1])j++;
		if(2*j>=i)ans=max(ans,n-i+2);
		else if(ck1(j+1,i-j+1)||ck2(j,i-j))ans=max(ans,n-i+2);
	}
	write(ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7692kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

1000

result:

wrong answer 1st lines differ - expected: '6', found: '1000'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 0ms
memory: 14688kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

1

result:

wrong answer 1st lines differ - expected: '9', found: '1'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%