RT

几乎对着板子代码抄的

最后统计 endpos 等价类表示起始位置的个数的时候一开始用的 dfs, MLE

后来改成了拓扑排序 WA + RE + TLE

Code：

SAM

int to[Maxn << 1][26], len[Maxn << 1], link[Maxn << 1], cnt = 1, last = 1;
LL siz[Maxn << 1], Max;

void extend(int c) {
  int cur = ++cnt; len[cur] = len[last] + 1;
  int p = last;
  while(p && (!to[p][c])) {
    to[p][c] = cur;
    p = link[p];
  }
  if(!p) link[cur] = 1;
  else {
    int q = to[p][c];
    if(len[p] + 1 == len[q]) link[cur] = q;
    else {
      int cl = ++cnt; len[cl] = len[p] + 1;
      for(int i = 0; i < 26; ++i) to[cl][i] = to[q][i];
      link[cl] = link[q]; link[q] = link[cur] = cl;
      while(p && to[p][c] == q) to[p][c] = cl, p = link[p];
    }
  }
  last = cur;
  siz[cur] = 1;
}

dfs

struct e {
  int to, nxt;
} b[Maxn << 1];
int head[Maxn], ecnt;
void add(int u, int v) {b[++ecnt] = (e) {v, head[u]}; head[u] = ecnt;}
string s;
void dfs(int t) {
  for(int i = head[t]; i; i = b[i].nxt) {
    dfs(b[i].to); siz[t] += siz[b[i].to];
  }
  if(siz[t] > 1) Max = max(Max, 1ll * len[t] * siz[t]);
}
}

toposort：

int ind[Maxn];
queue<int> que;

int main() {
  cin >> s; int n = s.size();
  for(int i = 0; i < n; ++i) extend(s[i] - 'a');
  for(int i = 2; i <= cnt; ++i) ind[link[i]]++;
  for(int i = 1; i <= cnt; ++i) if(!ind[i]) que.push(i);
  while(!que.empty()) {
    int t = que.front(); que.pop();
    if(siz[t] > 1) Max = max(Max, 1ll * siz[t] * len[t]);
    siz[link[t]] += siz[t];
    ind[link[t]]--; if(!ind[link[t]] && link[t]) que.push(link[t]); 
  }
  printf("%lld", Max);
  return 0;
}