P2922 [USACO08DEC]Secret Message G

洛谷AC通道！

纪念一下第一次不看题解一遍过的字符串（字典树）题。

题目非常简单，建立 \(Trie\) 树，每个节点记录 \(sum\) 和 \(end\), 分别代表经过这个点的字符串数量和以这个节点为结尾的字符串数量。

查询时遍历 \(Trie\) 树，同时不停累加 \(end\) 值，即模板串小于匹配串的情况。到达模板串的尾端时，加上 \(sum\) 值，即匹配串小于模板串的情况。自处注意特判匹配串超出 \(Trie\) 树长度，即最终到达节点为 \(0\) 的情况。同时记得在累加 \(sum\) 时减去该节点的 \(end\), 避免重复计算。

#include 
using namespace std;
#define N 1000010
#define ll long long

template 
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ;
}

struct tree{
	int ch[2];
	int end;    // 有多少在这结尾 
	int sum;    // 有多少经过这 
} t[N];
int id = 0; 

int b[N], c[N];
int a[N];  
int n, m;  

void build(int now, int len){  // 插入
	for(int i = 1; i <= len; i++){
		if(!t[now].ch[a[i]]) t[now].ch[a[i]] = ++id; 
		now = t[now].ch[a[i]]; 
		t[now].sum++; 
	}
	t[now].end++;
	return ; 
}

int query(int now, int len){
	int sum = 0;
	for(int i = 1; i <= len; i++){
		now = t[now].ch[a[i]];
		if(!now) break; 
		sum += t[now].end;
	}
	if(now) sum += t[now].sum - t[now].end;
	return sum; 
}

int main(){
//	freopen("hh.txt", "r", stdin); 
	read(m), read(n);
	for(int i = 1; i <= m; i++){
		int k; read(k); 
		for(int j = 1; j <= k; j++)
			read(a[j]);
		build(0, k);  
	}
	for(int i = 1; i <= n; i++){
		int k; read(k);
		for(int j = 1; j <= k; j++)
			read(a[j]);
		printf("%d\n", query(0, k)); 
	}
	return 0; 
}