后缀自动机处理多字符串字串相关问题。

首先，和后缀数组一样，用分割符连接各字符串，然后建一个后缀自动机。

我们定义一个节点代表的字符串为它原本代表的所有串去除包含分割符后的串。每个节点代表的字符串的数量可以用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 
      
        11 #include 
       
         12 #include 
        
          13 #include 
         
           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]
          
           >=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]
           
            =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 sam182 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 substring196 dodp();197 // build parent tree and its dfs order198 build();199 dfs(0);200 // calc echo string's effort201 for( int i=1; i<=n; i++ )202 effort( shead[i] );203 // bfs to calc the sum of subans204 bfs();205 // query the answer of eacho string206 for( int i=1; i<=n; i++ )207 query( shead[i] );208 printf( "\n" );209 }