第一道AC自动机题目。
记一下对AC自动机的理解吧：
AC自动机=Trie+KMP。即在Trie上应用KMP思想，实现多Pattern的匹配问题。
复杂度是预处理O(segma len(P))，匹配是O(len(T))。应该也是下界了。
它预处理做了以下事情：
1、建立所有Pattern的Trie
2、计算出fail和last数组
匹配时和KMP很像。
我对fail和last的理解:
对于一棵Trie，上面的一个节点对应一个字符串，该字符串是root到该节点的路径上，边代表的字符连接起来的。
fail[i]是一个指针，它指向一个节点f，使得f代表的字符串是i代表的字符串最长的一个后缀（所以f的深度一定比i小）。
last[i]也是一个指针，它指向一个节点f，使得f代表的字符串是i代表的字符串的一个后缀且该后缀也是一个Pattern。（如果不存在则指向根）。
我们将根节点代表的字符串理解成空串，空串是任何字符串的子串。
对于匹配过程，我们将Text串也想成一个由点和边组成的链，我们从最左边的点开始向右开始匹配。
我们以Text串的位置为阶段进行匹配，如果Trie的当前节点存在一条边，使得它代表的字符串和text串一致，就两边都前进。如果不存在，trie中的节点就不断通过fail向上跳，直到存在边或到达根，如果存在边就同时向下走，否则（即到达根且根也没有对应边），那就trie保持在根，text串到下一节点。
然后每到一个新的trie节点就查看是否匹配到（要用到last数组）.
去重的几种方式：
1、set
2、sort+unique
3、mark+vector
各有特点，
set是实时添加和查询，O(nlogn)。
sort+unique是添加完后查询（多用于离散话），也是O(nlogn)（常数比前者小）。
mark+vector，要求范围较小（10^7以内），O(n)
/**************************************************************
Problem: 2754
User: idy002
Language: C++
Result: Accepted
Time:1320 ms
Memory:13264 kb
****************************************************************/ #include <cstdio>
#include <cctype>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#define maxn 100010
using namespace std; typedef vector<int> String; int gint() {
int rt;
char ch, opt;
while( !isdigit(ch=getchar()) ) opt=ch;
rt=ch-'';
while( isdigit(ch=getchar()) ) rt=rt*+ch-'';
return rt;
} int n, m;
int ans[][maxn];
String str[maxn], ss;
bool mark[maxn];
vector<int> in; struct AC {
map<int,int> son[maxn];
set<int> st;
vector<int> stk[maxn];
int fail[maxn], last[maxn], ntot; void insert( int id, String &p ) {
int u=;
for( int i=; i<p.size(); i++ ) {
int c=p[i];
if( !son[u][c] ) son[u][c] = ++ntot;
u=son[u][c];
}
stk[u].push_back(id);
}
void build() {
queue<int> qu;
for( map<int,int>::iterator it=son[].begin(); it!=son[].end(); ++it ) {
int v=it->second;
qu.push(v);
fail[v] = last[v] = ;
}
while(!qu.empty()) {
int u=qu.front();
qu.pop();
for( map<int,int>::iterator it=son[u].begin(); it!=son[u].end(); ++it ) {
int c=it->first;
int v=it->second;
int w=fail[u];
while( w && !son[w][c] ) w=fail[w];
int x=son[w][c];
fail[v] = x;
last[v] = stk[x].size() ? x : last[x];
qu.push(v);
}
}
}
void add( int u ) {
if( !u ) return;
add(last[u]);
for( int t=; t<stk[u].size(); t++ ) {
if( mark[stk[u][t]] ) continue;
mark[stk[u][t]] = true;
in.push_back( stk[u][t] );
}
}
void search( int id, String &T ) {
st.clear();
int u=;
for( int i=; i<T.size(); i++ ) {
while( u && !son[u][T[i]] ) u=fail[u];
u=son[u][T[i]];
if( stk[u].size() ) add(u);
else add(last[u]);
}
ans[][id] += in.size();
for( int t=; t<in.size(); t++ ) {
ans[][in[t]]++;
mark[in[t]]=false;
}
in.clear();
}
}ac; int main() {
n = gint();
m = gint();
for( int i=,z; i<=n; i++ ) {
z = gint();
while(z--) str[i].push_back( gint() );
str[i].push_back(-);
z = gint();
while(z--) str[i].push_back( gint() );
}
for( int i=,z; i<=m; i++ ) {
ss.clear();
z = gint();
while(z--) ss.push_back( gint() );
ac.insert( i, ss );
}
ac.build();
for( int i=; i<=n; i++ )
ac.search( i, str[i] );
for( int i=; i<=m; i++ )
printf( "%d\n", ans[][i] );
for( int i=; i<=n; i++ )
printf( "%d%s", ans[][i], i==n ? "" : " " );
}