hdu 1247 Hat’s Words 字典树

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[50005][50];
struct f
{
    int next[30];
    int v;
    void ff()
    {
        memset(next,-1,sizeof(next));
        v=0;
    }
};f tree[1000000];
int cut=0;
void buld(char *s1)
{
    int i,k=0,su;
    for (i=0;s1[i]!=‘\0‘;i++)
    {
        su=s1[i]-‘a‘;
        if (tree[k].next[su]==-1)
        {
            cut++;
            tree[k].next[su]=cut;
            tree[cut].ff();
        }
        k=tree[k].next[su];
    }
    tree[k].v=1;
    return ;
}
int find(char *s1)
{
    int i,k=0,su,len;
    len=strlen(s1);
    for (i=0;i<len;i++)
    {
        su=s1[i]-‘a‘;
        if (tree[k].next[su]==-1) break;
        k=tree[k].next[su];
    }
    if (i==len&&tree[k].v) return 1;
    return 0;
}
int main()
{
     int p=0,i,j,len,k,d;
     char sl[50],sr[50];
     tree[cut].ff();
     while (~scanf("%s",s[p]))
     {
         buld(s[p]);
         p++;
     }
     for (i=0;i<p;i++)
     {
         len=strlen(s[i]);
         for (j=0;j<len;j++)
         {
             memset(sr,‘\0‘,sizeof(sr));
             memset(sl,‘\0‘,sizeof(sl));
            for (k=0;k<j;k++) sl[k]=s[i][k];
            sl[j]=‘\0‘;
            for (k=j,d=0;k<len;k++,d++) sr[d]=s[i][k];
            sr[len]=‘\0‘;
             if (find(sl)&&find(sr))
             {
                 printf("%s\n",s[i]);
                 break;
             }
         }
     }
     return 0;
}