Description
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0NXYFhGd192UvwVe0lmdhJ3ZvwFM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2LcNHaYF2bwhVY1w2RiZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39TM4cjNyITMyIjNwEDM4EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
Input
輸入一行,小寫字母組成的字元串,代表項鍊上珍珠的顔色,可能從項鍊的任意位置開始。
Output
輸出一行,拼接後對稱的新項鍊最長長度。
Sample Input
Sample Output
Data Constraint
Solution
- 先貼一個 Twilight 大神的 Solution :
- 我用的掃描線+并查集,時間複雜度 O(N∗α(N)) 。
- 由于本人較弱,再貼一個 Crazy 大爺的掃描線大法:
- 黑白點染色。用并查集記錄一團不可行的點的最左的點的位置。
- 倒着做一遍,順便染色和統計答案即可。
Code
#include<cstdio>
using namespace std;
const int N=+;
int n,ans,id,tot1,tot2;
int first1[N],next1[N],en1[N];
int first2[N],next2[N],en2[N];
int p[N],f[N];
bool col[N];
char s[N];
inline int min(int x,int y)
{
return x<y?x:y;
}
inline int max(int x,int y)
{
return x>y?x:y;
}
inline void Manacher()
{
for(int i=n;i;i--) s[i<<]=s[i],s[i<<|]='#';
n=n<<|,s[]='#',s[]='$';
for(int i=;i<=n;i++)
{
p[i]=p[id]+id>i?min(p[id*-i],p[id]+id-i):;
while(s[i-p[i]]==s[i+p[i]]) p[i]++;
if(p[i]+i>p[id]+id) id=i;
}
for(int i=;i<=n;i++) p[i]--;
}
inline void insert1(int x,int y)
{
next1[++tot1]=first1[x];
first1[x]=tot1;
en1[tot1]=y;
}
inline void insert2(int x,int y)
{
next2[++tot2]=first2[x];
first2[x]=tot2;
en2[tot2]=y;
}
int get(int x)
{
return f[x]==x?x:f[x]=get(f[x]);
}
int main()
{
char ch=getchar();
while(ch>='a' && ch<='z') s[++n]=ch,ch=getchar();
for(int i=n<<;i>n;i--) s[i]=s[i-n];
n<<=,Manacher();
for(int i=;i<=n;i++)
{
f[i]=i;
insert1(i-p[i],i);
insert2(i+p[i],i);
}
for(int i=n;i;i--)
{
for(int j=first2[i];j;j=next2[j])
{
int x=min(n,en2[j]+(n>>)),y=!col[x]?x:get(x)-;
ans=max(ans,y-en2[j]);
}
for(int j=first1[i];j;j=next1[j])
{
int x=en1[j];
col[x]=true;
if(col[x-]) f[get(x)]=x-;
if(col[x+]) f[get(x+)]=x;
}
}
printf("%d",ans);
return ;
}