hdoj-1247-Hat’s Words-字典樹
#include
#include
#include
#include
using namespace std;
const int N=30;
const int MAX=50005;
char word[MAX][30];
struct node
{
bool temp;
node *next[N];
node()
{
temp=false;
memset(next,0,sizeof(next));
//next是表示每層有多少種類的數，如果只是小寫字母，則26即可，
//若改為大小寫字母，則是52，若再加上數字，則是62了
}
};
void insert(node *rt,char *s)
{
int i,t;
i=0;
node *p=rt;
while(s[i])
{
t=s[i++]-'a';
if(p->next[t]==NULL)
p->next[t]=new node();
p=p->next[t];
}
p->temp=true;//指向單詞尾部
}
bool search(node *rt,char s[])
{
int i,top;
i=top=0;
int stack[MAX];
node *p=rt;
while(s[i])
{
int t=s[i++]-'a';
if(p->next[t]==NULL)
return false;
p=p->next[t];
if(p->temp&&s[i]) //找到含有子單詞的分割點 並且該字符還沒結束
stack[top++]=i; //將這個分割點入棧 ，然後循環判斷剩下的部分是否含有一個子單詞
}
while(top) //從這些分割點開始找
{
bool ok=true; //標記是否找到
i=stack[--top]; //第一個分割點
p=rt;
while(s[i])
{
int t=s[i++]-'a';
if(p->next[t]==NULL)
{
ok=false; //沒有找到
break;
}
p=p->next[t];
}
if(ok&&p->temp)
return true;
}
return false;
}
int main()
{
int i=0;
node *rt=new node();
while(gets(word[i]))
{
insert(rt,word[i]);
i++;
}
for(int j=0;j
