#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<cmath>#define N 1010005using namespace std;int sa[N],rank[N],height[N],b[N],c[N],d[N],m,pos[205],rmq[N][30],s[N],len[205];char ch[N];void getsa(int n,int m){ for (int i=0;i<=m;i++) b[i]=0; for (int i=1;i<=n;i++) b[s[i]]++; for (int i=1;i<=m;i++) b[i]+=b[i-1]; for (int i=n;i>=1;i--) c[b[s[i]]--]=i; int t=0; for (int i=1;i<=n;i++) { if (s[c[i]]!=s[c[i-1]]) t++; rank[c[i]]=t; } int j=1; while (j<=n) { for (int i=0;i<=n;i++) b[i]=0; for (int i=1;i<=n;i++) b[rank[i+j]]++; for (int i=1;i<=n;i++) b[i]+=b[i-1]; for (int i=n;i>=1;i--) c[b[rank[i+j]]--]=i; for (int i=0;i<=n;i++) b[i]=0; for (int i=1;i<=n;i++) b[rank[i]]++; for (int i=1;i<=n;i++) b[i]+=b[i-1]; for (int i=n;i>=1;i--) d[b[rank[c[i]]]--]=c[i]; int t=0; for (int i=1;i<=n;i++) { if (rank[d[i]]!=rank[d[i-1]]||rank[d[i]]==rank[d[i-1]]&&rank[d[i]+j]!=rank[d[i-1]+j]) t++; c[d[i]]=t; } for (int i=1;i<=n;i++) rank[i]=c[i]; if (t==n) break; j*=2; } for (int i=1;i<=n;i++) sa[rank[i]]=i;}void getheight(int n){ int k=0; for (int i=1;i<=n;i++) { if (k) k--; int j=sa[rank[i]-1]; while (i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++; height[rank[i]]=k; }}void get_rmq(int n){ int lg=log(n)/log(2); for (int i=1;i<=n;i++) rmq[i][0]=height[i]; for (int j=1;j<=lg;j++) for (int i=1;i<=n-(1<<j)+1;i++) rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);}int get_min(int l,int r){ int lg=log(r-l+1)/log(2); return min(rmq[l][lg],rmq[r-(1<<lg)+1][lg]);}int efl(int pos,int len,int n){ int l=1,r=pos-1; while (l<=r) { int mid=(l+r)/2; if (get_min(mid+1,pos)>=len) r=mid-1; else l=mid+1; } return r+1;}int efr(int pos,int len,int n){ int l=pos+1,r=n; while (l<=r) { int mid=(l+r)/2; if (get_min(pos+1,mid)>=len) l=mid+1; else r=mid-1; } return l-1;}int main(){ scanf("%d",&m); int n=0,tot=123; for (int i=1;i<=m;i++) { scanf("%s",ch); len[i]=strlen(ch);pos[i]=n+1; for (int j=0;j<len[i];j++) s[++n]=ch[j]; s[++n]=tot++; } getsa(n,tot); getheight(n); get_rmq(n); for (int i=1;i<=m;i++) { int l=efl(rank[pos[i]],len[i],n),r=efr(rank[pos[i]],len[i],n);;
