BZOJ3473 - Click Here
Description
给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串？
Input
第一行两个整数n，k。
接下来n行每行一个字符串。
Output
一行n个整数，第i个整数表示第i个字符串的答案。
Solutions
按照这种题目的套路，大概就是需要一个能够匹配所有子串的数据结构，然后在数据结构上解决问题。
考虑对所有字符串建立广义SAM，这样所有子串都能够被匹配到。接下来的问题是如何求出所有状态的在n个字符串中的出现次数。
一个比较暴力的做法是，对于所有的后缀状态，暴力的往link节点更新，如果遇到已经更新的节点就结束。这个做法看似是$O(T^2)$级别的，但实际上的上界为$O(T \sqrt {T})$
不严谨的证明一下结论。
假设字符串数为$N$，平均长度为$L$，显然有$T=NL$。对于第$k$个加入的字符串，由于每个节点至多只会被更新一次，因此最坏的更新次数为$min(kL,L^2)$，总次数为$\sum_k min(kL,L^2)$。
对于上诉和式有$\sum_k min(kL,L^2) \leq min(\sum_k kL, \sum_k L^2)=min(n^2L,nL^2)$。显然当$n^2L=nL^2$时，不等式取到上界，因此$n=L=\sqrt T$。
处理出所有节点的出现次数后，就可以直接在SAM上DP求出每个状态贡献的答案了。
时间复杂度$O(T |\sum| + T \sqrt T)$
CODE
CODE - Click Here