LCP

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll trie[1005006][27];
ll node[1500006];
ll lenval[1500006],temp[1500016];
ll maxlen,n,cur;
string str[500005];
void ins(string s)
{
    ll root=1;
    ll i,j;
    for(i=0;i<s.size();i++)
    {
        j=s[i]-'a';
        if(trie[root][j]==0)
        {
            cur++;
            trie[root][j]=cur;
        }
        root=trie[root][j];
        node[root]++;
    }
}
void qry(string s)
{
    ll root=1;
    ll i,j,cursub=0;
    ll sz=s.size();
    for(i=0;i<=sz+10;i++)
    temp[i]=0;
    for(i=0;i<s.size();i++)
    {
        j=s[i]-'a';
        root=trie[root][j];
        temp[i+1]=node[root]-1;
    }
    for(i=s.size();i>=1;i--)
    {
        temp[i]-=cursub;
        cursub+=temp[i];
        lenval[i]+=temp[i];
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll i,j,k;
    cin>>n;
    cur=1;
    for(i=1;i<=n;i++)
    {
        cin>>str[i];
        ins(str[i]);
        j=str[i].size();
        maxlen=max(maxlen,j);
    }
    for(i=1;i<=n;i++)
    {
        qry(str[i]);
    }
    j=n*(n-1);
    j/=2;
    k=0;
    for(i=1;i<=maxlen;i++)
    {
        lenval[i]/=2;
        k+=lenval[i];
    }
    lenval[0]=j-k;
    for(i=0;i<=maxlen;i++)
    cout<<lenval[i]<<" ";
    return 0;
}