马拉车（manacher）算法

马拉车算法是用来查找一个字符串的最长回文子串的线性方法

code

const int N = 2e5 + 10;

int n;
char a[N], s[N];
int p[N];

void init()
{
    int k = 0;
    s[k ++ ] = '$', s[k ++ ] = '#';
    for (int i = 0; i < n; i ++ )
    	s[k ++ ] = a[i], s[k ++ ] = '#';
    s[k ++ ] = '^';
    n = k;
}

void manacher()
{
    int mr = 0, mid;
    for (int i = 0; i < n; i ++ )
    {
        if (i < mr) p[i] = min(p[mid * 2 - i], mr - i);
        else p[i] = 1;
        while (s[i - p[i]] == s[i + p[i]])
            p[i] ++ ;
        if (i + p[i] > mr) 
        {
            mr = i + p[i];
            mid = i;
        }
    }
}

后缀数组

后缀数组算法，就是求出后缀次序的算法，也就是对所有后缀排个序的高效算法。

code

const int N = 1e6 + 10;

int n, m;
char s[N];
int sa[N];//排名为i的是第几个后缀
int rk[N];//第i个后缀的排名是多少
int height[N];//sa[i]与sa[i-1]的最长公共前缀
int x[N], y[N], c[N];

void get_sa()
{
    //按第一个字母进行基数排序
    for (int i = 1; i <= n; i ++ ) c[x[i] = s[i]] ++ ;//统计每个字符的个数
    for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];//前缀和求小于当前字符的字符个数
    for (int i = n; i; i -- ) sa[c[x[i]] -- ] = i;//逆序使得相同字母的相对位置不变
    for (int k = 1; k <= n; k <<= 1)//倍增
    {
        //分成长度为k的两段，以第一段为第一关键字，第二段为第二关键字进行排序
        int num = 0;

        //按第二关键字排序,y为排序结果
        for (int i = n - k + 1; i <= n; i ++ ) y[ ++ num] = i;
        //第二关键字为空，直接加入排序
        for (int i = 1; i <= n; i ++ )
            if (sa[i] > k) y[ ++ num] = sa[i] - k;  
        //i开头的第2段为i+k开头的第1段

        //基数排序
        for (int i = 1; i <= m; i ++ ) c[i] = 0;
        for (int i = 1; i <= n; i ++ ) c[x[i]] ++ ;
        for (int i = 2; i <= m; i ++ ) c[i] += c[i - 1];
        for (int i = n; i; i -- )
            sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;
        swap(x, y);

        //离散化
        x[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i ++ )
        x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        //判断排名为i和i-1的后缀的两段是否分别相等

        if (num == n) break;
        m = num; 
    }
}

void get_height()
{
    for (int i = 1; i <= n; i ++ ) rk[sa[i]] = i;
    //排名为i的后缀的排名为i
    for (int i = 1, k = 0; i <= n; i ++ )
    {
        if (rk[i] == 1) continue;
        if (k) k -- ;
        int j = sa[rk[i] - 1];//比当前后缀排名小1的后缀
        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++ ;
        height[rk[i]] = k;
    }
}

JZTXT

字符串

马拉车（manacher）算法

后缀数组