题目传送门

　　传送门

题目大意

　　给定n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串

 /**

  * bzoj

  * Problem#3473

  * Accepted

  * Time: 788ms

  * Memory: 41208k

  */

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 using namespace std;

 typedef bool boolean;

 template <typename T>

 void pfill(T* pst, const T* ped, T val) {

     for ( ; pst != ped; *(pst++) = val);

 }

 const int N = 2e5 + ;

 const int bzmax = ;

 typedef class SparseTable {

     public:

         int n;

         int *ar;

         int log2[N];

         int f[N][bzmax];

         SparseTable() {    }

         void init(int n, int* ar) {

             this->n = n;

             this->ar = ar;

             log2[] = ;

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

                 log2[i] = log2[i >> ] + ;

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

                 f[i][] = ar[i];

             for (int j = ; j < bzmax; j++)

                 for (int i = ; i + ( << j) -  < n; i++)

                     f[i][j] = min(f[i][j - ], f[i + ( << (j - ))][j - ]);

         }

         int query(int l, int r) {

             int d = log2[r - l + ];

 //            int rt = min(f[l][d], f[r - (1 << d) + 1][d]);

 //            cerr << l << " " << r << " " << rt << '\n';

             return min(f[l][d], f[r - ( << d) + ][d]);

         }

 }SparseTable;

 typedef class Pair3 {

     public:

         int x, y, id;

         Pair3() {    }

         Pair3(int x, int y, int id):x(x), y(y), id(id) {    }

 }Pair3;

 typedef class SuffixArray {

     protected:

         Pair3 T1[N], T2[N];

         int cnt[N];

     public:

         int n;

         char *str;

         int sa[N], rk[N], hei[N];

         SparseTable st;

         void set(int n, char* str) {

             this->n = n;

             this->str = str;

             memset(sa, , sizeof(sa));

             memset(rk, , sizeof(rk));

             memset(hei, , sizeof(hei));

         }

         void radix_sort(Pair3* x, Pair3* y) {

             int m = max(n, );

             memset(cnt, , sizeof(int) * m);

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

                 cnt[x[i].y]++;

             for (int i = ; i < m; i++)

                 cnt[i] += cnt[i - ];

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

                 y[--cnt[x[i].y]] = x[i];

             memset(cnt, , sizeof(int) * m);

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

                 cnt[y[i].x]++;

             for (int i = ; i < m; i++)

                 cnt[i] += cnt[i - ];

             for (int i = n - ; ~i; i--)

                 x[--cnt[y[i].x]] = y[i];

         }

         void build() {

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

                 rk[i] = str[i];

             for (int k = ; k <= n; k <<= ) {

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

                     T1[i] = Pair3(rk[i], rk[i + k], i);

                 for (int i = n - k; i < n; i++)

                     T1[i] = Pair3(rk[i], , i);

                 radix_sort(T1, T2);

                 int diff = ;

                 rk[T1[].id] = ;

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

                     rk[T1[i].id] = (T1[i].x == T1[i - ].x && T1[i].y == T1[i - ].y) ? (diff) : (++diff);

                 if (diff == n)

                     break;

             }

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

                 sa[--rk[i]] = i;

         }

         void get_height() {

             for (int i = , j, k = ; i < n; i++, (k) ? (k--) : ()) {

                 if (rk[i]) {

                     j = sa[rk[i] - ];

                     while (i + k < n && j + k < n && str[i + k] == str[j + k])    k++;

                     hei[rk[i]] = k;

                 }

             }

         }

         void init_st() {

             st.init(n, hei);

         }

         int lcp(int x1, int x2) {

             if (x1 == x2)

                 return n - x1 + ;

             x1 = rk[x1], x2 = rk[x2];

             if (x1 > x2)

                 swap(x1, x2);

             return st.query(x1 + , x2);

         }

         int compare(int l1, int r1, int l2, int r2) {

             int len_lcp = lcp(l1, l2);

             int len1 = r1 - l1 + , len2= r2 - l2 + ;

             if (len_lcp >= len1 && len_lcp >= len2)

                 return ;

             if (len_lcp < len1 && len_lcp < len2)

                 return (str[l1 + len_lcp] < str[l2 + len_lcp]) ? (-) : ();

             return (len_lcp >= len1) ? (-) : ();

         }

         int query(int u, int v) {    // u, v -> sa

             if (u == v)

                 return n - sa[u];

             return st.query(u + , v);

         }

         const int& operator [] (int p) {

             return sa[p];

         }

         const int& operator () (int p) {

             return hei[p];

         }

 } SuffixArray;

 typedef class IndexedTree {

     public:

         int s;

         int *a;

         IndexedTree() {    }

         IndexedTree(int n) : s(n) {

             a = new int[(s + )];

             pfill(a + , a + n + , );

         }

         ~IndexedTree() {

             delete[] a;

         }

         void add(int idx, int val) {

             for ( ; idx <= s; idx += (idx & (-idx)))

                 a[idx] += val;

         }

         int query(int idx) {

             int rt = ;

             for ( ; idx; idx -= (idx & (-idx)))

                 rt += a[idx];

             return rt;

         }

         int query(int l, int r) {

             return query(r) - query(l - );

         }

 } IndexedTree;

 typedef class Graph {

     protected:

         int dfs_clock;

     public:

         vector<int>* g;

         int *fa;

         int *in, *out;

         int *sz, *zson;

         int *dep, *top;

         Graph() {    }

         Graph(vector<int>* g, int n) : dfs_clock(), g(g) {

             fa = new int[(n + )];

             in = new int[(n + )];

             out = new int[(n + )];

             sz = new int[(n + )];

             zson = new int[(n + )];

             dep = new int[(n + )];

             top = new int[(n + )];

             dfs1(, );

             dfs2(, true);

         }

         ~Graph() {

 #define rem(__) delete[] __;

             rem(fa) rem(in) rem(out) rem(sz) rem(zson) rem(dep) rem(top)

         }

         void dfs1(int p, int fa) {

             dep[p] = ((fa) ? (dep[fa] + ) : ());

             in[p] = ++dfs_clock;

             this->fa[p] = fa;

             sz[p] = ;

             int mx = -, id = -, e;

             for (unsigned i = ; i < g[p].size(); i++) {

                 e = g[p][i];

                 dfs1(e, p);

                 sz[p] += sz[e];

                 if (sz[e] > mx)

                     mx = sz[e], id = e;

             }

             out[p] = dfs_clock;

             zson[p] = id;

         }

         void dfs2(int p, boolean ontop) {

             top[p] = ((ontop) ? (p) : (top[fa[p]]));

             if (~zson[p])

                 dfs2(zson[p], false);

             for (int i = , e; i < (signed) g[p].size(); i++) {

                 e = g[p][i];

                 if (e == zson[p])

                     continue;

                 dfs2(e, true);

             }

         }

         int lca(int u, int v) {

             while (top[u] ^ top[v]) {

                 if (dep[top[u]] < dep[top[v]])

                     swap(u, v);

                 u = fa[top[u]];

             }

             return (dep[u] < dep[v]) ? (u) : (v);

         }

 } Graph;

 #define pii pair<int, int>

 int n, L, K;

 int id[N];

 char str[N];

 SuffixArray sa;

 int endp[N >> ];

 char _str[N >> ];

 vector<int> endpos[N >> ];

 inline void init() {

     L = ;

     scanf("%d%d", &n, &K);

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

         scanf("%s", _str);

         if (i > ) {

             id[L] = -;

             str[L] = '#'; //"!@#$%^&*()-+"[i % 11];

             L += ;

         }

         for (char* p = _str; *p; p++) {

             id[L] = i;

             str[L] = *p;

             L++;

         }

         endp[i] = L;

     }

     sa.set(L, str);

     sa.build();

     sa.get_height();

     sa.init_st();

 }

 int cnt_node;

 vector<int> g[N << ];

 int d[N << ];

 int build_suffix_tree(int l, int r) {

     int curid = ++cnt_node;

     d[curid] = sa.query(l, r);

     if (l == r) {

         int p = sa[l];

         if (id[p] > )

             endpos[id[p]].push_back(curid);

         return curid;

     }

     for (int p = l, j, L, R, mid; p <= r; p = j + ) {

         L = p, R = r;

         char x = str[sa[p] + d[curid]];

         while (L <= R) {

             mid = (L + R) >> ;

             if (str[sa[mid] + d[curid]] == x)

                 L = mid + ;

             else

                 R = mid - ;

         }

         j = L - ;

         L = build_suffix_tree(p, j);

         g[curid].push_back(L);

     }

     return curid;

 }

 int res[N << ];

 void dfs(int p, Graph& G, IndexedTree& it) {

     res[p] = (it.query(G.in[p], G.out[p]) >= K) ? (d[p]) : (res[G.fa[p]]);

     for (int i = ; i < (signed) g[p].size(); i++) {

          dfs(g[p][i], G, it);

     }

 }

 inline void solve() {

     while (cnt_node)

         g[cnt_node--].clear();

     build_suffix_tree(, L - );

     IndexedTree it (cnt_node);

     Graph graph (g, cnt_node);

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

         it.add(graph.in[endpos[i][]], );

         for (int j = ; j < (signed) endpos[i].size(); j++) {

             it.add(graph.in[endpos[i][j]], );

             int g = graph.lca(endpos[i][j], endpos[i][j - ]);

             it.add(graph.in[g], -);

         }

     }

     dfs(, graph, it);

     for (int i = , p, l; i <= n; i++) {

         long long ans = ;

         for (int j = ; j < (signed) endpos[i].size(); j++) {

             p = endpos[i][j], l = d[p];

             ans += min(endp[i] - (L - l), res[p]);

         }

         printf("%lld ", ans);

     }

 }

 int main() {

     init();

     solve();

     return ;

 }