Description：

给定 $N$ 字符串，求出每个字符串没有在别的字符串中出现过的字串个数。

$1\leqslant N\leqslant 10^5,1\leqslant \sum|S|\leqslant 10^5$

Solution：

建出广义后缀自动机，在建的时候为每个 $last$ 标上它的颜色，因为每个 $last$ 一定只属于一个子串，然后在 $parent$ 树上 $dfs$ 为每个点标颜色，最后统计一下答案即可，每个点对答案的贡献是 $s[i].maxl-s[s[i].par].maxl$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXL 100010

char S[MAXL];

struct node

{

	int col;

	int maxl,par;

	int tr[26];

	node(){col = 0;}

}s[MAXL << 1];

int root = 1,ptr = 1,last = 1;

int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

void extend(int k)

{

	int p = last;

	int np = newnode(s[p].maxl + 1);

	for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

	if(p == 0)s[np].par = root;

	else

	{

		int q = s[p].tr[k];

		if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

		else

		{

			int nq = newnode(s[p].maxl + 1);

			memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

			s[nq].par = s[q].par;

			s[q].par = s[np].par = nq;

			for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

		}

	}

	last = np;

	return;

}

struct edge

{

	int to,nxt;

}e[MAXL << 1];

int edgenum = 0;

int lin[MAXL << 1];

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

void dfs(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		dfs(e[i].to);

		if(s[k].col == 0)s[k].col = s[e[i].to].col;

		else if(s[k].col != -1 && s[e[i].to].col != s[k].col)s[k].col = -1;

	}

	return;

}

int ans[MAXL];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%s",S + 1);

		int l = strlen(S + 1);

		last = 1;

		for(int j = 1;j <= l;++j)

		{

			extend(S[j] - 'a');

			s[last].col = i;

		}

	}

	for(int i = 2;i <= ptr;++i)add(s[i].par,i);

	dfs(1);

	for(int i = 2;i <= ptr;++i)

	{

		if(s[i].col > 0)

		{

			ans[s[i].col] += s[i].maxl - s[s[i].par].maxl;

		}

	}

	for(int i = 1;i <= n;++i)printf("%d\n",ans[i]);

	return 0;

}