USACO DEC17,Platinum

USACO DEC17,Platinum"/>

USACO DEC17,Platinum

        第一次打usaco，感觉题目还挺有趣的。（为啥感觉美国人的英语比日、俄的英语还要难读呢）

Standinfg Out from the Herd.

        题意：给n个字符串，对每个字符串求有多少本质不同的子串只在这个字符串中出现。

        这题我直接求了一个广义后缀自动机，然后给每个点一个标记表示这个点对应的子串是否只在某个字符串中出现。然后随便统计一下就做完了。O(N)。

AC代码如下：

#include<bits/stdc++.h>
#define N 200009
using namespace std;int n; long long ans[N]; char s[N];
struct sam{int tot,fst[N],nxt[N],ch[N][26],fa[N],len[N],f[N];sam(){ tot=1; }void calc(int x,int y){ f[x]=(f[x] && f[x]!=y?-1:y); }int add(int k,int c,int p){int np=++tot; calc(np,k); len[np]=len[p]+1;for (; p && !ch[p][c]; p=fa[p]) ch[p][c]=np;if (!p){fa[np]=1; return np;}int q=ch[p][c];//cerr<<"	"<<k<<' '<<c<<' '<<p<<' '<<q<<' '<<len[p]<<' '<<len[q]<<endl;if (len[q]==len[p]+1) fa[np]=q; else{int nq=++tot; len[nq]=len[p]+1;//cerr<<nq<<endl;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q]; fa[q]=fa[np]=nq;//cerr<<q<<' '<<np<<endl;for (; p && ch[p][c]==q; p=fa[p]) ch[p][c]=nq;}return np;}void dfs(int x){int y;for (y=fst[