@[wen_kr](/space/show?uid=25308)
by ywy_c_asm @ 2018-12-12 15:54:16
%%%
ywy是我们的红太阳，没有它我们就会死
by shadowice1984 @ 2018-12-12 16:00:46
颜神%%%%%%%%
by enceladus @ 2018-12-12 16:42:43
这个点是随机数据
by Wen_kr @ 2018-12-12 18:18:09
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int m = 2000,n;
int buc[1010050],rnk[1010050],tp[1010050],sa[1030050],str[1020050];
int belong[1020500],height[1030050];
int len;
void get_sa()
{
memset(buc,0,sizeof(buc));
for(int i = 1;i <= len; ++ i) buc[rnk[i] = str[i]] ++;
for(int i = 1;i <= m; ++ i) buc[i] += buc[i - 1];
for(int i = len;i >= 1; -- i) sa[buc[rnk[i]] --] = i;
for(int k = 1;;k <<= 1)
{
int tot = 0;
for(int i = len - k + 1;i <= len; ++ i) tp[++tot] = i;
for(int i = 1;i <= len; ++ i) if(sa[i] > k) tp[++tot] = sa[i] - k;
for(int i = 0;i <= m; ++ i) buc[i] = 0;
for(int i = 1;i <= len; ++ i) buc[rnk[i]] ++;
for(int i = 1;i <= m; ++ i) buc[i] += buc[i - 1];
for(int i = len;i >= 1; -- i) sa[buc[rnk[tp[i]]] --] = tp[i];
swap(rnk,tp);
rnk[sa[1]] = 1;
tot = 1;
for(int i = 2;i <= len; ++ i)
rnk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + k] == tp[sa[i - 1] + k]) ? tot : ++tot;
if(tot >= len) return ;
m = tot;
}
}
void get_height()
{
int k = 0;
for(int i = 1;i <= len; ++ i) rnk[sa[i]] = i;
for(int i = 1;i <= len; ++ i)
{
if(k) k --;
int j = sa[rnk[i] - 1];
while(str[i + k] == str[j + k]) k ++;
height[rnk[i]] = k;
}
}
char strx[1001005];
int ans[105][105];
int cur[105];
int main()
{
int n;
scanf("%d",&n);
for(int i = 1;i <= n; ++ i)
{
scanf(" %s",strx + 1);
int strl = strlen(strx + 1);
for(int j = 1;j <= strl; ++ j)
str[++len] = strx[j],belong[len] = i;
str[++len] = 1000 + i;
}
get_sa();get_height();
for(int i = 2;i <= len; ++ i)
{
for(int j = 1;j <= n; ++ j)
cur[j] = min(cur[j],height[i]);
cur[belong[sa[i - 1]]] = height[i];
int curx = belong[sa[i]];
for(int j = 1;j <= n; ++ j)
ans[curx][j] = ans[j][curx] = max(ans[j][curx],cur[j]);
}
for(int i = 1;i <= n; ++ i)
{
for(int j = 1;j <= n; ++ j)
if(j != i) printf("%d ",ans[i][j]);
printf("\n");
}
}
```
这是 std，没有任何常数优化的版本，没开O2，稳过...
@[ywy_c_asm](/space/show?uid=125124)
by Wen_kr @ 2018-12-12 18:19:32