复杂
度
3.Manacher
求以某点为中⼼的最⻓回⽂
每次进⼊while 时，必定R 会右移
R 和C 两个单调指针，复杂
度
4.后缀数组
对⼀个字符串的所有后缀排序，并可以求出排名相邻的后缀的lcp
for (int  i =1;i <=l ;i ++){
int  j =nxt [i -1];
while (j &&s [i ]!=s [j +1]) j =nxt [j ];
nxt [i ]=j +(s [i ]==s [j +1];
}
for (int  i =1;i <=l ;i ++) s [++l ]='#',s [++l ]=t [i ];s [++l ]='#';for (int  i =1,C ,R ;i <=l ;i ++)//回⽂中⼼C 回⽂最右端点
{
p [i ]=i <=R ?min (p [C *2-i ],R -i ):1;
while (s [i +p [i ]]==s [i -p [i ]]&&i +p [i ]<=l &&i -p [i ]>=1)
p [i ]++;
if (i +p [i ]-1>R ) R =i +p [i ]-1,C =i ;
Ans =max (Ans ,p [i ]-1);//最⻓回⽂⼦串
字符串转数组怎么转}
复杂
度
5.(⼴义)后缀⾃动机
int  cmp (int  i ,int  j ,int  k ) {return  y [i ]==y [j ]&&y [i +k ]==y [j +k ];}
void  Sort ()
{
for (int  i =1;i <=m ;i ++) t [i ]=0;
for (int  i =1;i <=l ;i ++) t [x [i ]]++;
for (int  i =1;i <=m ;i ++) t [i ]+=t [i -1];
for (int  i =l ;i >=1;k --) SA [t [x [y [i ]]]--]=y [i ];
}
void  GetSA ()
{
for (int  i =1;i <=l ;i ++) x [i ]=s [i ],y [i ]=i ;Sort ();
for (int  k =1,p =0;k <=l ;k <<=1)
{
for (int  i =l -k +1;i <=l ;i ++) y [++p ]=i ;
for (int  i =1;i <=l ;i ++) if (SA [i ]>k ) y [++p ]=SA [i ]-k ;        Sort ();swap (x ,y );x [SA [1]]=p =1;
for (int  i =2;i <=l ;i ++) x [SA [i ]]=cmp (SA [i ],SA [i -
1],k )?p :++p ;
if (p ==m ) return ;m =p ;p =0;
}
for (int  i =1;i <=l ;i ++) rk [SA [i ]]=i ;
for (int  i =1,j =0;i <=l ;i ++)
{
while (s [i +j ]==s [SA [rk [i ]-1]+j ]) j ++;
h [rk [i ]]=j ;if (j ) j --;
}
}
⽤⼀个DAG 表⽰⼀个串中所有的⼦串。⼴义即多个串，要求BFS 建SAM 。3+2+3⾏
⾄于⼴义SAM 为什么要加两个特判呢，我觉得我之前的博客并没有讲清楚
如果不加特判，直
接，那么会加⼊⽆⽤节点，该节点有连边、有fail ⽗亲，但是在DAG 上⽆⼊度。绝⼤多数情况下，不加特判是没有问题的。
加了特判之后，没有⽆⽤节点（可能有但是没有连出去的边），并且在后⽅确定了下⼀个接节点的位置，能够保证对以后⽆影响。当在要记录串插到哪⼀个位置、⽤lct 维护该位置fail 树上的信息时，肯定就不能存⽆⽤位置了。
加特判是⼀个好习惯。没有加在BZOJ5408会WA ，当然数据要精⼼构造才能卡掉。
//SAM void  Extend (int  c )
{
int  f =lst ,p =++nod ;lst =p ;len [p ]=len [f ]+1;
while (f &&!ch [f ][c ]) ch [f ][c ]=p ,f =fa [f ];
if (!f ) {fa [p ]=1;return ;}
int  x =ch [f ][c ],y =++nod ;
if (len [x ]==len [f ]+1) {fa [p ]=x ;nod --;return ;}
memcpy (ch [y ],ch [x ],sizeof (ch [y ]));
len [y ]=len [f ]+1;fa [y ]=fa [x ];fa [x ]=fa [p ]=y ;
while (f &&ch [f ][c ]==x ) ch [f ][c ]=y ,f =fa [f ];
}
复杂
度
6.回⽂树
⽤⼀个DAG 表⽰⼀个串中所有的回⽂⼦串。
其每个点表⽰以其结尾的最⻓回⽂后缀//⼴义SAM int  Extend (int  f ,int  c )
{
if (ch [f ][c ]&&len [ch [f ][c ]]==len [f ]+1) return  ch [f ]
[c ];//！
int  p =++nod ,ff =0;len [p ]=len [f ]+1;
while (f &&!ch [f ][c ]) ch [f ][c ]=p ,f =fa [f ];
if (!f ) {fa [p ]=1;return  p ;}
int  x =ch [f ][c ],y =++nod ;
if (len [x ]==len [f ]+1) {fa [p ]=x ;nod --;return  p ;}    if (len [p ]==len [f ]+1) ff =1;//！
memcpy (ch [y ],ch [x ],sizeof (ch [y ]));
len [y ]=len [f ]+1;fa [y ]=fa [x ];fa [x ]=fa [p ]=y ;    while (f &&ch [f ][c ]==x ) ch [f ][c ]=y ,f =fa [f ];
return  ff ?y :p ;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。