hdu 1247 Hat’s Words

map水过去了，240ms的样子。。。用字典树应该比map快多了吧。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<algorithm>
using namespace std;
map<string, int> abc;
char s[50005][1000];
int main()
{
    char k[1000];
    abc.clear();
    int tot = 0;
    while (~scanf("%s", k))
    {
        abc[k] = 1;
        strcpy(s[tot], k);
        tot++;
    }
    int i, j;
    for (i = 0; i < tot; i++)
    {
        for (j = 1; j <= strlen(s[i]) - 1; j++)
        {
            char temp1[50] = { '' };
            char temp2[50] = { '' };
            strncpy(temp1, s[i], j);
            strncpy(temp2, s[i] + j, strlen(s[i]) - j);
            if (abc[temp1] == 1 && abc[temp2])
            {
                printf("%s
", s[i]);
                break; 
            }
        }
    }
    return 0;
}