hdu 1247 Hat’s Words 字典树

//	hdu 1247 Hat’s Words 字典树
//
//	题目大意：
//		
//		在一些字符串中，找到这样字符串：由两个其他的字符串构成
//
//	解题思路：
//
//		字典树，先将这些字符串插入到字典树中，然后枚举断点，如果
//		字符串的前后两段都找到了，输出该串即可~
//
//	感悟：
//
//		这道题目的话，就是字典树上的暴力嘛，细节方面还是要多多注意
//		val值还是不能少哟~因为查找到了该串，不一定是一个单词，可能
//		是中间的一个节点，即某个字符串的前缀~~~FIGHTING!

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX_N = 400000;

char s[50005][100];

struct Trie{
	int ch[MAX_N][26];
	int val[MAX_N];
	int sz;

	void init(){
		memset(ch[0],0,sizeof(ch[0]));
		sz = 1;
		val[0] = 0;
	}

	int idx(char c){
		return c - 'a';
	}

	void insert(char *s,int v){
		int u = 0;
		int n = strlen(s);
		for (int i=0;i<n;i++){
			int c = idx(s[i]);
			if (!ch[u][c]){
				memset(ch[sz],0,sizeof(ch[sz]));
				val[sz] = 0;
				ch[u][c] = sz++;
			}
			u = ch[u][c];
		}
		val[u] = v;
	}

	int query(char *s,int st,int ed){
		int u = 0;
		//int n = strlen(s);
		for (int i=st;i<ed;i++){
			int c = idx(s[i]);
			if (!ch[u][c])
				return 0;
			u = ch[u][c];
		}
		return val[u];
	}

}trie;

int main(){
	//freopen("1.txt","r",stdin);
	int cnt = 1;
	char x[100];
	trie.init();
	while(scanf("%s",x)!=EOF){
		memcpy(s[cnt],x,sizeof(x));
		trie.insert(x,cnt);
		cnt++;
	}
	
	for (int i = 1;i < cnt;i++){
		int n = strlen(s[i]);
		for (int j = 1;j < n;j++)
			if (trie.query(s[i],0,j) && trie.query(s[i],j,n)){
				printf("%s\n",s[i]);
				break;
			}
	}
	return 0;
}

hdu 1247 Hat’s Words 字典树

原文：http://blog.csdn.net/timelimite/article/details/47192945