MnZn求助
查看原帖
MnZn求助
310581
ethan0328楼主2023/9/22 21:14

为什么我把代码全扔函数里跑的更快了

700ms700ms -> 150ms150ms

调用函数不应该更慢吗

原来的码:

#include<bits/stdc++.h>
using namespace std;
const int N=1.1e7+10;
int n,maxn,ans[N*2];
string s;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int mid=0,r=0,x;
	string str;
	cin>>str;
	s="!#";
	for(int i=0;i<str.length();i++)
	{
		s=s+str[i];
		s=s+"#";
	}
	s=s+"$";
	n=s.length();
	for(int i=1;i<n-1;i++)
	{
		x=mid*2-i;
		if(i<r)
		{
			ans[i]=min(ans[x],r-i);
		}else
		{
			ans[i]=0;
		}
		while(s[i+ans[i]+1]==s[i-ans[i]-1])
		{
			ans[i]++;
		}
		if(i+ans[i]>r)
		{
			r=i+ans[i];
			mid=i;
		}
	}
	for(int i=1;i<n-1;i++)
	{
		maxn=max(maxn,ans[i]);
	}
	cout<<maxn;
}

改过后的码:

#include<bits/stdc++.h>
using namespace std;
const int N=1.1e7+10;
int n,ans[N*2];
int manachar(string str)
{
	int mid=0,r=0,x,maxn=0;
	string s;
	s="!#";
	for(int i=0;i<str.length();i++)
	{
		s+=str[i];
		s+="#";
	}
	s+="$";
	n=s.length();
	for(int i=1;i<n-1;i++)
	{
		x=mid*2-i;
		if(i<r)
		{
			ans[i]=min(ans[x],r-i);
		}else
		{
			ans[i]=0;
		}
		while(s[i+ans[i]+1]==s[i-ans[i]-1])
		{
			ans[i]++;
		}
		if(i+ans[i]>r)
		{
			r=i+ans[i];
			mid=i;
		}
	}
	for(int i=1;i<n-1;i++)
	{
		maxn=max(maxn,ans[i]);
	}
	return maxn;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	string s;
	cin>>s;
	cout<<manachar(s);
}
2023/9/22 21:14
加载中...