分析

做法非常多，有 的。好像复杂度都是 的。这里提供一种广义后缀自动机的做法。这里采用了绝对没有空节点的在线做法，空间为线性 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char ch[210][N];
int fa[N<<1],si[N<<1],len[N<<1],nxt[N][26],last,size;
int insert(int c) {
    if(nxt[last][c]) {
        int p = last,q = nxt[last][c];
        if(len[p] + 1 == len[q]) {si[q]++;return q;}
        else {
            int cl = ++size;fa[cl] = fa[q];len[cl] = len[p] + 1;
            for(int i = 0;i < 26;i++) nxt[cl][i] = nxt[q][i];
            for(;p != -1 && nxt[p][c] == q;p = fa[p]) nxt[p][c] = cl;
            fa[q] = cl;si[cl]++;return cl;
        }
    }
    int cur=++size;len[cur] = len[last] + 1;si[cur] = 1;
    int p = last;for(;p != -1 && !nxt[p][c];p = fa[p]) nxt[p][c] = cur;
    if(p == -1) fa[cur] = 0;
    else {
        int q = nxt[p][c];if(len[q] == len[p] + 1) fa[cur] = q;
        else {
            int cl = ++size;fa[cl] = fa[q];len[cl] = len[q] + 1;
            for(int i = 0;i < 26;i++) nxt[cl][i] = nxt[q][i];
            for(;p != -1 && nxt[p][c] == q;p = fa[p]) nxt[p][c] = cl;
            fa[cur] = fa[q] = cl;
        }
    }
    return cur;
}
vector<int> G[N << 1];
void dfs(int x) {for(auto y:G[x]) dfs(y),si[x] += si[y];}
int main() {
    fa[0] = -1;
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;i++) {
        scanf("%s",ch[i] + 1);
        int len = strlen(ch[i] + 1);
        last = 0;
        for(int j = 1;j <= len;j++) last = insert(ch[i][j] - 'a');
    }
    for(int i = 1;i <= size;i++) G[fa[i]].push_back(i);dfs(0);
    for(int i = 1;i <= n;i++) {
        int len = strlen(ch[i] + 1);
        int u = 0;for(int j = 1;j <= len;j++) u = nxt[u][ch[i][j] - 'a'];
        printf("%d\n",si[u]);
    }
    return 0;
}