Warning: session_start(): open(/tmp/sess_f7905b17ef45a14b81a7cd6c6c7c7cc8, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
=====后缀数组复习=====
===什么是后缀数组===
将一个字符串的所有后缀按照字典序从小到大排序，我们记sa[i]表示排名第i的后缀在原串的开头位置。
===后缀数组可以用来干什么===
处理一系列关于子串/回文串/后缀子串/重复子串/公共子串/子串相似度的问题
===后缀数组模版===
build_sa函数
const int Len = 200000+5;
char s[Len];
int c[Len],sa[Len],val[Len],q[Len],newval[Len];
bool is_same(int a,int b,int hl,int len)
{
return val[a]==val[b]&&((a+hl>len&&b+hl>len)||(a+hl=0;i--)sa[--c[val[i]]] = i;
for(int d=1;;d++)
{
int hl = 1<<(d-1),id = 0;
for(i = 0;i=len)q[id++] = sa[i];
for(i = 0;i=hl)q[id++] = sa[i]-hl;
for(i = 0;i= 0;i--)sa[--c[val[q[i]]]] = q[i];
lim = 0;
for(i = 0;i
求height(排名为i的后缀和排名为i-1的后缀的最长公共前缀)和rank(开头为i的后缀的排名)的函数
void build_rank(int len)
{
for(int i= 0;i