hdu1247 字典树或者hash

      我用了两种方法，一个是hash，hash的时候用map实现的，第二种方法是字典树，字典树我们枚举每个一字符串，查找他的每一位，如果当前这一位是某个单词的最后一个字母，那么就重新跑到树的根节点，继续搜，搜到最后一个字母的时候，如果当前的这个字母是某个单词的最后一个那么就输出当前这个，还有就是注意一点，如果找到答案就直接break，不然后可能输出重复的，因为当前这个字符串可能被很多组合满足，还有就是不知道题目中有没有这样的数据 ab abab,这样不知道是否要输出abab，总之不用管就AC了，估计就是没有，要不就是题目说了我没注意。

字典树

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct Tree
{
    Tree *next[26];
    int mk;
}Tree;

Tree root;

char str[50005][100];

void Buid_Tree(char *str)
{
    int len = strlen(str);
    Tree *p = &root ,*q;
    for(int i = 0 ;i < len ;i ++)
    {
        int id = str[i] - 'a';
        if(p -> next[id] == NULL)
        {
             q = (Tree *) malloc(sizeof(Tree));
             q -> mk = 0;
             for(int j = 0 ;j < 26 ;j ++)
             q -> next[j] = NULL;
             p -> next[id] = q;
             p = p -> next[id];
        }
        else p = p -> next[id];
    }
    p -> mk = 1;
}

void solve(char *str)
{
    int len = strlen(str);
    Tree *p = &root;
    for(int i = 0 ;i < len ;i ++)
    {
        int id = str[i] - 'a';
        p = p -> next[id];
        if(p == NULL) break;
        if(p -> mk)
        {
            Tree *pp = &root;
            int mkk = 0;
            for(int j = i + 1 ;j < len && !mkk;j ++)
            {
                int idd = str[j] - 'a';
                pp = pp -> next[idd];
                if(pp == NULL) mkk = 1;
            }
            if(!mkk && pp -> mk)
            {
               printf("%s
" ,str);
               break;
            }
         }
     }
}
int main ()
{
    for(int i = 0 ;i < 26 ;i ++)
    root.next[i] = NULL;
    int n = 0;
    while(~scanf("%s" ,str[++n]))
    {
       Buid_Tree(str[n]);
    }
    for(int i = 1 ;i <= n ;i ++)
    solve(str[i]);
    return 0;
}


hash

#include<iostream>
#include<map>
#include<string>

using namespace std;

string str[55000];
map<string ,int>hash;

int main ()
{
    int n = 0 ,i;
    hash.clear();
    while(cin >> str[++n])
    {
        hash[str[n]] = 1;
    }
    for(i = 1 ;i <= n ;i ++)
    {
       int len = str[i].size();
       for(int k = 1 ;k < len ;k ++)
       {
           string s1(str[i] ,0 ,k);
           string s2(str[i] ,k ,len);
           if(hash[s1] && hash[s2])
           {
              cout<<str[i]<<endl;
              break;
           }
       }
     }
     //getchar();getchar();
    return 0;
}