bzoj

using namespace std;
 
const int maxnode = 1e6+100;
const int sigma_size = 26;
int n;
char s[maxnode];
 
int ch[maxnode][sigma_size];
int val[maxnode];
int f[maxnode];
int last[maxnode];
int sz;
int cnt[maxnode];
int id[maxnode];
int que[maxnode], qt;
 
void () {
    sz = 1;
    memset(ch[0], 0, sizeof(ch[0]));
}
 
int idx(char c) {
    return c - 'a';
}
 
void insert(char *s, int x, int v = 1) {
    int n = strlen(s);
    int u = 0;
    for (int i = 0; i < n; i++) {
        int c = idx(s[i]);
        if (!ch[u][c]) {
            ch[u][c] = sz;
            memset(ch[sz], 0, sizeof(ch[sz]));
            val[sz++] = 0;
        }
        u = ch[u][c];
        cnt[u]++;
    }
    val[u] = v;
    id[x] = u;
}
 
void getfail() {
    queue<int> q;
    f[0] = 0;
    for (int i = 0; i < sigma_size; i++) {
        int u = ch[0][i];
        if (u) {
            f[u] = last[u] = 0;
            q.push(u);
            que[++qt] = u;
        }
    }
    while (!q.empty()) {
        int r = q.front();
        q.pop();
        
        for (int c = 0; c < sigma_size; c++) {
            int u = ch[r][c];
            if (!u) {
                ch[r][c] = ch[f[r]][c];
                continue;
            }
            q.push(u);
            que[++qt] = u;
            int v = f[r];
            while (v && !ch[v][c])v = f[v];
            f[u] = ch[v][c];
            last[u] = val[f[u]] ? f[u] : last[f[u]];
        }
    }
    for(int i = qt; i; i--) cnt[f[que[i]]] += cnt[que[i]];
}
 
int main(){
    init();
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%s", s);
        insert(s, i);
    }
    getfail();
    for(int i = 1; i <= n; i++) printf("%dn", cnt[id[i]]);
    return 0;
}