[알고리즘 경기 진급 안내] 접두사 통계 (trie 트 리)

제목.
N 개의 문자열 S1, S2... SN 을 주어진 다음 M 번 질문 을 합 니 다. 주어진 문자열 T 에 대해 물 어 볼 때마다 S1 ~ SN 에 T 의 접두사 가 몇 개 있 는 지 물 어 봅 니 다.
입력 문자열 의 총 길 이 는 10 ^ 6 을 초과 하지 않 고 소문 자 만 포함 합 니 다.
입력 형식
첫 줄 에 정수 N, M 두 개 를 입력 하 십시오.
다음 N 줄 마다 문자열 Si 를 입력 하 십시오.
다음 M 줄 마다 문자열 T 를 물 어 봅 니 다.
출력 형식
모든 질문 에 정 수 를 출력 하여 답 을 표시 합 니 다.
각 답안 이 한 줄 을 차지 하 다.
입력 예시:

3 2
ab
bc
abc
abc
efg

출력 예시:

2
0

분석:

트 리 템 플 릿 문제

트 리 두 가지 템 플 릿 해법

코드

트 리 나무

#include 
#include 
using namespace std;
const int N=1e6+5,English=26;

typedef struct trie{
	int count;
	struct trie *children[English];
}trie;

char s[N];
int n,m;

//  trie    
trie* creat_trie_node(){ 
	trie *pnode=new trie();
	pnode->count=0;
	for(int i=0;ichildren[i]=NULL;
	}
	return pnode; 
}

// key  trie  
void trie_insert(trie *root,char *key){
	trie *node=root;
	char *p=key;
	while(*p){
		if(node->children[*p-'a']==NULL){
			node->children[*p-'a']=creat_trie_node();
		}
		node=node->children[*p-'a'];
		p++;
	}
	node->count++; 
}

//    trie  
void show_trie(trie *root){
	trie *node=root;
	if(node!=NULL){
		for(int i=0;ichildren[i]) {
				printf("%c ",i+'a');
				show_trie(node->children[i]);
			}
		}
	} 
}

// trie       
int trie_search(trie *root,char *key){
	trie *node=root;
	char *p=key;
	int ans=0;
	while(*p&&node!=NULL){
		ans+=node->count;
		node=node->children[*p-'a'];
		p++;
	}
	if(node!=NULL) ans+=node->count;
	return ans;
}


int main()
{
	cin>>n>>m;
	trie *root=creat_trie_node();
	for(int i=0;i>s;
		trie_insert(root,s);
//		show_trie(root);cout<>s;
		ans=trie_search(root,s);
		cout<

배열 시 뮬 레이 션 트 리

#include 
#include 
using namespace std;
const int N=1e6+5,M=5e5+5,W=26;

int trie[M][W],p[M],idx;
char s[N]; 
int n,m;

//k  trie    
void trie_insert(char *k){ 
	int t=0;
	for(int i=0;k[i];i++){
		int &x=trie[t][k[i]-'a'];
		if(!x) x=++idx;
		t=x;
	}
	p[t]++;
}

// trie     k 
int query(char *k){
	int t=0,ans=0;
	for(int i=0;k[i];i++){
		int &x=trie[t][k[i]-'a'];
		if(!x) break;
		t=x;
		ans+=p[t];
	}
	return ans;
}

int main()
{
	cin>>n>>m;
	for(int i=0;i>s;
		trie_insert(s);
	}
	for(int i=0;i>s;
		cout<