http://acm.hdu.edu.cn/showproblem.php?pid=1247
题意:
给出一些单词,问哪些单词可以正好由其他的两个单词首尾相连而成。
思路:
先将所有单独插入字典树,然后对于每一个单词,枚举它的分割点,去字典树中查找是否具有这两个单词。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = +; char s[maxn][];
int num = ; struct Trie
{
int son[];
int ends;
}t[maxn*]; void init(int x)
{
t[x].ends = ;
memset(t[x].son,,sizeof(t[x].son));
} void insert(char* s)
{
int u = , n = strlen(s);
for(int i=;i<n;i++)
{
int c = s[i]-'a';
if(!t[u].son[c])
{
num++;
init(num);
t[u].son[c] = num;
}
u = t[u].son[c];
}
t[u].ends = ;
} bool query(char* s)
{
int u = , n = strlen(s);
for(int i=;i<n;i++)
{
int c = s[i]-'a';
if(!t[u].son[c]) return false;
u = t[u].son[c];
}
if(t[u].ends == ) return true;
return false;
} int main()
{
//freopen("in.txt","r",stdin);
int tot = ;
char s1[],s2[];
while(~scanf("%s",s[tot++])) insert(s[tot-]);
for(int i=;i<tot;i++)
{
int len = strlen(s[i]);
for(int j=;j<len;j++)
{
memset(s1,,sizeof(s1));
memset(s2,,sizeof(s2));
strncpy(s1,s[i],j);
strncpy(s2,s[i]+j,len-j);
if(query(s1) && query(s2)) {printf("%s\n",s[i]);break;}
}
}
return ;
}