后缀自动机处理多字符串字串相关问题。
首先，和后缀数组一样，用分割符连接各字符串，然后建一个后缀自动机。
我们定义一个节点代表的字符串为它原本代表的所有串去除包含分割符后的串。每个节点代表的字符串的数量可以用DP来计算（不能用right集合来算了）。
对于原来n个串中的一个串，其所有前缀可以通过将该串放到自动机上跑来获得，对于某个前缀，其所有后缀包括在该前缀本身的节点以及parent树的祖先节点中。这样我们就获得访问某个串所有子串的技能了。
对于这道题，我们可以先建出后缀自动机，然后对于n个串中的每个串，找到包含其子串的所有节点（可以保证所有子串一定且唯一出现在某个节点中）。然后将它们的计数器+1。弄完后，对于每个节点，我们就可以知道其代表的串是n个串中多少个串的子串。
最后再对于每个串，找出所有字串（不同位置要区分），统计答案。
如果不同位置不区分，那么我们得到的节点不能重复。如果要区分，对于每个前缀，其parent树上的节点都要计算，即使以前被计算过（因为他们的结束位置不同，所以肯定要计算）。
1 /************************************************************** 2 Problem: 3473 3 User: idy002 4 Language: C++ 5 Result: Accepted 6 Time:728 ms 7 Memory:120928 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <cassert> 13 #include <algorithm> 14 #define N 200010 15 #define S 500010 16 #define P 18 17 using namespace std; 18 19 typedef long long dnt; 20 21 int n, k; 22 char buf[N], *shead[N]; 23 int son[S][27], pnt[S], val[S], ntot, last; 24 int head[S], dest[S], next[S], etot; 25 int dfn[S], dep[S], anc[S][P+1], idgr[S], stk[S], qu[S], top, bg, ed, idc; 26 dnt dp[S], eff[S]; 27 int log[S]; 28 29 void init() { 30 ntot = last = 0; 31 pnt[0] = -1; 32 } 33 void append( int c ) { 34 int p = last; 35 int np = ++ntot; 36 val[np] = val[p]+1; 37 while( p!=-1 && !son[p][c] ) 38 son[p][c]=np, p=pnt[p]; 39 if( p==-1 ) { 40 pnt[np] = 0; 41 } else { 42 int q=son[p][c]; 43 if( val[q]==val[p]+1 ) { 44 pnt[np] = q; 45 } else { 46 int nq = ++ntot; 47 memcpy( son[nq], son[q], sizeof(son[nq]) ); 48 val[nq] = val[p]+1; 49 pnt[nq] = pnt[q]; 50 pnt[q] = pnt[np] = nq; 51 while( p!=-1 && son[p][c]==q ) 52 son[p][c]=nq, p=pnt[p]; 53 } 54 } 55 last = np; 56 } 57 void make_topo() { 58 for( int u=0; u<=ntot; u++ ) { 59 for( int c=0; c<=26; c++ ) { 60 int v=son[u][c]; 61 if( !v ) continue; 62 idgr[v]++; 63 } 64 } 65 qu[bg=ed=1] = 0; 66 while( bg<=ed ) { 67 int u=qu[bg++]; 68 for( int c=0; c<=26; c++ ) { 69 int v=son[u][c]; 70 if( !v ) continue; 71 idgr[v]--; 72 if( idgr[v]==0 ) 73 qu[++ed] = v; 74 } 75 } 76 } 77 void dodp() { 78 make_topo(); 79 dp[0] = 1; 80 for( int i=1; i<=ed; i++ ) { 81 int u=qu[i]; 82 for( int c=1; c<=26; c++ ) { 83 int v=son[u][c]; 84 if( !v ) continue; 85 dp[v] += dp[u]; 86 } 87 } 88 } 89 void adde( int u, int v ) { 90 etot++; 91 dest[etot] = v; 92 next[etot] = head[u]; 93 head[u] = etot; 94 } 95 void build() { 96 for( int u=1; u<=ntot; u++ ) 97 adde( pnt[u], u ); 98 } 99 void dfs( int u ) { 100 dfn[u] = ++idc; 101 for( int p=1; p<=P && anc[u][p-1]; p++ ) 102 anc[u][p] = anc[anc[u][p-1]][p-1]; 103 for( int t=head[u]; t; t=next[t] ) { 104 int v=dest[t]; 105 dep[v] = dep[u]+1; 106 anc[v][0] = u; 107 dfs(v); 108 } 109 } 110 int lca( int u, int v ) { 111 if( dep[u]<dep[v] ) swap(u,v); 112 int t=dep[u]-dep[v]; 113 for( int p=0; t; p++,t>>=1 ) 114 if( t&1 ) u=anc[u][p]; 115 if( u==v ) return u; 116 for( int p=log[dep[u]]; anc[u][0]!=anc[v][0]; p-- ) 117 if( anc[u][p]!=anc[v][p] ) u=anc[u][p],v=anc[v][p]; 118 return anc[u][0]; 119 } 120 void fetch( char *s ) { 121 top = 0; 122 int u = 0; 123 for( int i=0; s[i]; i++ ) { 124 int c=s[i]-'a'+1; 125 u = son[u][c]; 126 assert(u!=0); 127 stk[++top] = u; 128 } 129 } 130 bool cmp( int u, int v ) { 131 return dfn[u]<dfn[v]; 132 } 133 void effort( char *s ) { 134 fetch(s); 135 sort( stk+1, stk+1+top, cmp ); 136 eff[stk[1]] += 1; 137 for( int i=2; i<=top; i++ ) { 138 int u=stk[i]; 139 int ca=lca(u,stk[i-1]); 140 eff[u] += 1; 141 eff[ca] -= 1; 142 } 143 } 144 void bfs() { 145 qu[bg=ed=1] = 0; 146 while( bg<=ed ) { 147 int u=qu[bg++]; 148 for( int t=head[u]; t; t=next[t] ) { 149 int v=dest[t]; 150 qu[++ed] = v; 151 } 152 } 153 for( int i=ed; i>=1; i-- ) { 154 int u=qu[i]; 155 for( int t=head[u]; t; t=next[t] ) { 156 int v=dest[t]; 157 eff[u] += eff[v]; 158 } 159 } 160 dp[0] = 0; 161 for( int i=2; i<=ed; i++ ) { 162 int u=qu[i]; 163 if( eff[u]>=k ) { 164 dp[u] = dp[pnt[u]]+dp[u]; 165 } else { 166 dp[u] = dp[pnt[u]]; 167 } 168 } 169 } 170 void query( char *s ) { 171 fetch(s); 172 sort( stk+1, stk+1+top, cmp ); 173 dnt rt = 0; 174 for( int i=1; i<=top; i++ ) { 175 int u=stk[i]; 176 rt += dp[u]; 177 } 178 printf( "%lld ", rt ); 179 } 180 int main() { 181 // input and build sam 182 scanf( "%d%d", &n, &k ); 183 init(); 184 char *buf_cur = buf; 185 for( int i=1; i<=n; i++ ) { 186 shead[i] = buf_cur; 187 scanf( "%s", shead[i] ); 188 for( int j=0; shead[i][j]; j++ ) 189 append( shead[i][j]-'a'+1 ); 190 append( 0 ); 191 buf_cur += strlen(shead[i]) + 1; 192 } 193 log[0] = -1; 194 for( int i=1; i<=ntot; i++ ) log[i] = log[i>>1]+1; 195 // dodp to calc the number of real substring 196 dodp(); 197 // build parent tree and its dfs order 198 build(); 199 dfs(0); 200 // calc echo string's effort 201 for( int i=1; i<=n; i++ ) 202 effort( shead[i] ); 203 // bfs to calc the sum of subans 204 bfs(); 205 // query the answer of eacho string 206 for( int i=1; i<=n; i++ ) 207 query( shead[i] ); 208 printf( " " ); 209 }