后缀数组的讲解：https://wenku.baidu.com/view/ed1be61e10a6f524ccbf85fd.html
题意:
给你一个字符串,要你求出这个串中的最长回文字串,如果存在多个,则输出第一次出现的那个.
分析:
来自：https://blog.csdn.net/u013480600/article/details/23946429
首先将原字符串逆序连接在原字符串后面,不过中间添加一个字符$,然后在新字符串尾加个0即可.
求sa和height数组.假设原字符串长n,从0到n-1,那么新字符串长2*n+2(因为加了$和尾0),且从0到2*n-1.
如上图所示,我们只需要从0到n-1位置枚举,看看以当前位置i为中心的奇数回文串和偶数回文串最长为多少即可.
对于奇数回文串:比较新串的后缀i和后缀2*n-i的最长公共前缀即可.
假设这个LCP=x,那么以i为中心的奇数最长回文串长度=x*2-1.(对应上图的情况1,自己仔细想想看看是不是).
对于偶数回文串:比较新串的后缀i和后缀2*n-i+1的最长公共前缀即可.
假设这个LCP=x,那么以i为中心的偶数最长回文串长度=x*2.(对应上图的情况2,自己仔细想想看看是不是).
下面的问题是:如何求出两个后缀的LCP呢?由刘汝佳的书可知,两个后缀i和j的LCP为(假设rank[i]<rank[j]):
LCP=min( height[rank[i]+1], height[rank[i]+2] ,…, height[rank[j]] )
=RMQ(rank[i]+1,rank[j]).
所以我们对height数组在范围[1 , 2*n+1]区间维护一个RMQ即可.(因为height[0]指的是尾0无意义,且RMQ一般是从1开始的)
注意:数组要开两倍大.
/*后缀数组求最长回文子串*/
#include<bits/stdc++.h>
using namespace std;
/** suffix array* 倍增算法 O(n*logn)* 待排序数组长度为n,放在0~n-1中,在最后面补一个0* da(str, sa, rank, height, n, m);* 例如:* n = 8;* num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ }; 注意num最后一位为0,其他大于0* rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 }; rank[0~n-1]为有效值,rank[n]必定为0无效值* sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 }; sa[1~n]为有效值,sa[0]必定为n是无效值* height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 }; height[2~n]为有效值* 稍微改动可以求最长公共前缀，需要注意两串起始位置相同的情况* 另外需要注意的是部分数组需要开两倍空间大小*/
///rank[i] 第i个后缀的排名; SA[i] 排名为i的后缀位置; Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
///c[i] 计数排序辅助数组; tp[i] rank的辅助数组(计数排序中的第二关键字),与SA意义一样。
///a为原串
const int MAXN = 20010;int t1[MAXN];
int t2[MAXN];
int c[MAXN]; // 求SA数组需要的中间变量,不需要赋值// 待排序的字符串放在s数组中,从s[0]到s[n-1],长度为n,且最大值小于m,
// 除s[n-1]外的所有s[i]都大于0,r[n-1]=0
// 函数结束以后结果放在sa数组中
bool cmp(int *r, int a, int b, int l)
{return r[a] == r[b] && r[a + l] == r[b + l];
}void da(int str[], int sa[], int rank[], int height[], int n, int m)
{n++;int i, j, p, *x = t1, *y = t2; // 第一轮基数排序,如果s的最大值很大,可改为快速排序for (i = 0; i < m; i++){c[i] = 0;}for (i = 0; i < n; i++){c[x[i] = str[i]]++;}for (i = 1; i < m; i++){c[i] += c[i-1];}for (i = n - 1; i >= 0; i--){sa[--c[x[i]]] = i;}for (j = 1; j <= n; j <<= 1){p = 0;//直接利用sa数组排序第二关键字for (i = n - j; i < n; i++){y[p++] = i; //后面的j个数第二关键字为空的最小}for (i = 0; i < n; i++){if (sa[i] >= j){y[p++] = sa[i] - j; //这样数组y保存的就是按照第二关键字排序的结果}}// 基数排序第一关键字for (i = 0; i < m; i++){c[i] = 0;}for (i = 0; i < n; i++){c[x[y[i]]]++;}for (i = 1; i < m; i++){c[i] += c[i - 1];}for (i = n - 1; i >= 0; i--){sa[--c[x[y[i]]]] = y[i]; // 根据sa和x数组计算新的x数组}swap(x, y);p = 1;x[sa[0]] = 0;for (i = 1; i < n; i++){x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;}if (p >= n){break;}m = p; // 下次基数排序的最大值}int k = 0;n--;for (i = 0; i <= n; i++){rank[sa[i]] = i;}for (i = 0; i < n; i++){if (k){k--;}j = sa[rank[i] - 1];while (str[i + k] == str[j + k]){k++;}height[rank[i]] = k;}
}int _rank[MAXN], height[MAXN];
int RMQ[MAXN];
int mm[MAXN];int best[20][MAXN];void initRMQ(int n)
{mm[0] = -1;for (int i = 1; i <= n; i++){mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];}for (int i = 1; i <= n; i++){best[0][i] = i;}for (int i = 1; i <= mm[n]; i++){for (int j = 1; j + (1 << i) - 1 <= n; j++){int a = best[i - 1][j];int b = best[i - 1][j + (1 << (i - 1))];if (RMQ[a] < RMQ[b]){best[i][j] = a;}else{best[i][j] = b;}}}
}int askRMQ(int a, int b)
{int t;t = mm[b - a + 1];b -= (1 << t) - 1;a = best[t][a];b = best[t][b];return RMQ[a] < RMQ[b] ? a : b;
}int lcp(int a, int b)
{a = _rank[a];b = _rank[b];if (a > b){swap(a,b);}return height[askRMQ(a + 1, b)];
}char str[MAXN];
int r[MAXN];
int sa[MAXN];int main()
{while (scanf("%s", str) == 1){int len = (int)strlen(str);int n = 2 * len + 1;for (int i = 0; i < len; i++){r[i] = str[i];}for (int i = 0; i < len; i++){r[len + 1 + i] = str[len - 1 - i];}r[len] = 1;r[n] = 0;da(r, sa, _rank, height, n, 128);for (int i = 1; i <= n; i++){RMQ[i]=height[i];}initRMQ(n);int ans = 0, st = 0;int tmp;for (int i = 0; i < len; i++){tmp = lcp(i, n - i); //偶对称if (2 * tmp > ans){ans = 2 * tmp;st = i - tmp;}tmp=lcp(i, n - i - 1); //奇数对称if (2 * tmp - 1 > ans){ans = 2 * tmp - 1;st = i - tmp + 1;}}str[st + ans] = 0;printf("%s\n", str + st);}return 0;
}