为什么我把代码全扔函数里跑的更快了
700ms -> 150ms
调用函数不应该更慢吗
#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);
}